Sorting Algorithms

Internal

• Data Structures and Algorithms

Overview

Many programs use sorting as an intermediate step, and that is why sorting is considered a fundamental operation in computer science.

The sorting problem if formally defined as follows: given a sequence of n numbers (a₁, a₂, ... a_n) provided as input, the algorithm must produce as output a permutation (reordering) (a^'₁, a^'₂, ... a^'_n) of the input sequence such that a^'₁ ≤ a^'₂ ≤ ... ≤ a^'_n. A specific input sequence is called an instance of the sorting problem. Although conceptually we are sorting a sequence, the input comes to the sorting function as an array with n elements.

The numbers we wish to sort are also known as keys. In practice, it is rarely the case when the keys exist in isolation. Usually they are part of a larger structure called record, which also contains satellite data.

Sorting algorithms characteristics:

• in place: a sorting algorithm is said to sort the input numbers "in place" if it rearranges the numbers within the input array, while at most a constant number of elements are stored outside the array at any time.
• stability

The i^th order statistic of a set of n numbers is the i^th smallest number in the set.

Sorting Algorithms

Key Comparison Sorting Algorithms

A sorting algorithm may compare keys, and in this case it is said to be a key comparison algorithm. It can be demonstrated that a key comparison algorithm cannot perform better than n lg n. The worst-case running time of comparison sort algorithms is Ω(n lgn).

• Insertion sort
• Selection sort
• Merge sort
• Heap sort
• Quick sort

Non-Comparison Sorting Algorithms

• Counting sort
• Radix sort
• Bucket sort