Comparison of Sorting Algorithms (notes)

1. Selection-Sort:

Certainly, the selection-sort algorithm is a poor choice in any application, since it runs in O(n^2) time even in the best-case.

2. Insertion-Sort

If implemented well, the running time of insertion-sort is O(n+m), where m is the number if inversions (the number of pairs of elements out of order). Thus, insertion-sort is an excellent algorithm for sorting small sequences (say, less than 50 elements), because small sequences necessarily have few inversions.

And also, insertion-sort is quite effective for sorting sequences that are already "almost" sorted.

But the O(n^2)-time performance of insertions-sort makes it a poor choice outside of these special contexts.

3. Merge-Sort

Merge-sort, on the other hand, runs in O(nlogn) time in the worst-case, which is optimal for comparison-based sorting methods.

Merge-sort is an excellent algorithms for situations where the input cannot all ft into main memory, but must be stored in blocks on an external memory device, such as disk. Thus, for external memory sorting, the merge-sort algorithm tends to minimize the total number of disk reads and writes needed, which makes the merge-sort algorithm superior in such context.

Java uses merge-sort for Object arrays and quick-sort for primitive arrays.

4. Quick-Sort

Experimental studies have shown that id an input sequence can fit entirely in main memory, then the in-place versions of quick-sort and heap-sort run faster than merge-sort.

Still, its O(n^2) time worst-case performance makes quick-sort a poor choice in real-time applications where we must guarantee on the time needed to complete a sorting operation.

5. Heap-Sort

In real-time scenarios where we have a fixed amount of time to perform a sorting operation and the input data can fit into main memory, the heap-sort algorithm is probably the best choice. It runs in O(nlogn) worst-case time and can easily be made to execute in-place.

6. Bucket-Sort and Radix-Sort

Finally, if our application involves sorting entries with small integer keys or d-tuples of small integer keys, then bucket-sort and radix-sort is an excellent choice, for it run in O(d(n+N)) time, where [0, N+1] is the range of integer keys (and d=1 for bucket sort). Thus, if d(n + N) is significantly "below" the nlogn function, then this sorting method should run faster than even quick-sort or heap-sort.