Sort Additional Info

My notes on sorting algorithm comparison:

Space complexity :

Quicksort - O(n) total, O(n) aux

Mergesort - O(n) total, O(n) aux

Insertion sort - O(n)

Bubble sort - O(1)

Heap sort - O(1) aux

Selection sort - O(n) total, O(1) aux

Stable :

Quicksort - typical in-place sort is not stable; stable versions exist

Mergesort - Yes

Insertion sort - Yes

Bubble sort - Yes

Heap sort - No

Selection sort - No

In-Place:

Quicksort - in place version exists

Mergesort - No

Insertion sort - Yes

Bubble sort - Yes

Heap sort - Yes

Selection sort - Yes

Insertion sort:

    Best case - sorted input O(N)

    Worst case - reverse sorted input O(N2)

    Avg case - O(N2)

The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. 

However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten.

Merge sort:

    Best/Avg/Worst - O(nlogN)

Although heapsort has the same time bounds as merge sort, it requires only Θ(1) auxiliary space instead of merge sort's Θ(n). 

On typical modern architectures, efficient quicksort implementations generally outperform mergesort for sorting RAM-based arrays.

On the other hand, merge sort is a stable sort and is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list: in this situation it is relatively easy to implement a merge sort in such a way that it requires only Θ(1) extra space, and the slow random-access performance of a linked list makes some other algorithms (such as quicksort) perform poorly, and others (such as heapsort) completely impossible.

As of Perl 5.8, merge sort is its default sorting algorithm (it was quicksort in previous versions of Perl). In Java, the Arrays.sort() methods use merge sort or a tuned quicksort depending on the datatypes and for implementation efficiency switch to insertion sort when fewer than seven array elements are being sorted. Python uses Timsort, another tuned hybrid of merge sort and insertion sort, that has become the standard sort algorithm in Java SE 7, on the Android platform, and in GNU Octave.

Quick sort:

1. Quicksort also competes with mergesort, another recursive sort algorithm but with the benefit of worst-case O(n^2)  and best/average O(n log n) running time. 

    2. Mergesort is a stable sort, unlike standard in-place quicksort and heapsort, and can be easily adapted to operate on linked lists and very large lists stored on slow-to-access media such as disk storage or network attached storage

Heap sort :

Heapsort primarily competes with quicksort, another very efficient general purpose nearly-in-place comparison-based sort algorithm.

Quicksort is typically somewhat faster due to some factors, but the worst-case running time for quicksort is O(n2), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk. See quicksort for a detailed discussion of this problem and possible solutions.

Thus, because of the O(n log n) upper bound on heapsort's running time and constant upper bound on its auxiliary storage, embedded systems with real-time constraints or systems concerned with security often use heapsort.[citation needed]

Heapsort also competes with merge sort, which has the same time bounds. Merge sort requires Ω(n) auxiliary space, but heapsort requires only a constant amount. Heapsort typically runs faster in practice on machines with small or slow data caches, and does not require as much external memory. On the other hand, merge sort has several advantages over heapsort:

Merge sort on arrays has considerably better data cache performance, often outperforming heapsort on modern desktop computers because merge sort frequently accesses contiguous memory locations (good locality of reference); heapsort references are spread throughout the heap.

Heapsort is not a stable sort; merge sort is stable.

Merge sort parallelizes well and can achieve close to linear speedup with a trivial implementation; heapsort is not an obvious candidate for a parallel algorithm.

Merge sort can be adapted to operate on singly linked lists with O(1) extra space. Heapsort can be adapted to operate on doubly linked lists with only O(1) extra space overhead.[citation needed]

Merge sort is used in external sorting; heapsort is not. Locality of reference is the issue.

Introsort is an alternative to heapsort that combines quicksort and heapsort to retain advantages of both: worst case speed of heapsort and average speed of quicksort.