The complexity of sorting
Actually, there are more efficient algorithms for sorting:
• Quick sort - O(n lg n) average case time complexity [1].

• Heap sort - O(n lg n) worst case time complexity [2].

There is a sense in which O(n lg n) is the most efficient a general sorting algorithm can be.

A striking example of the relative efficiency of four different sorting algorithms is available from Andrew Kitchen at the Rochester Institute of Technology (click on their logo).

Note: By "general" we mean an algorithm that will operate on a standard processor, without special features. For example there are faster algorithms that require the use of multiprocessors operating in parallel.

The quick sort function sorts elements of data structures using a divide and conquer approach. This means the function resolves part of the problem and then recursively solves increasingly smaller partitions of the problem until eventually the whole problem is solved. This is part of the reason the quick sort is also called the Partition-Exchange Sort.

Each time the function recurses, a "key" value of the structure is selected to be positioned. The function then repeatedly scans through the structure from two directions. Values less than the key are passed to the left side of the structure and values that are greater than the key are passed to the right side of the structure. These "left to right" and "right to left" scans and swaps continue until a flag condition tells them to stop. This occurs when the structure can be divided into two sorted partitions. The key is then "switched into its final position". Next the quick sort function is called to sort the partition that contains the values that are less than the key. Then the quick sort function is called to sort the partition that contains the values that are greater than the key. The above algorithm continues until a condition indicates that the structure is sorted.

The heap sort algorithm looks very much like a selection sort but through the use of a data structure called a "heap" the process is speeded up considerably.

A heap sort algorithm that works by first organizing the data to be sorted into a special type of binary tree called a heap. The heap itself has, by definition, the largest value at the top of the tree, so the heap sort algorithm must also reverse the order. It does this with the following steps:

1. Remove the topmost item (the largest) and replace it with the rightmost leaf. The topmost item is stored in an array.
2. Re-establish the heap.
3. Repeat steps 1 and 2 until there are no more items left in the heap.
4. The sorted elements are now stored in an array.

A heap sort is especially efficient for data that is already stored in a binary tree. In many cases, however, the quick sort algorithm is more efficient.

CS1104 Main Page
Last Updated 2000/07/28
© J.A.N. Lee, based on a small original by L. Heath, 2000