1) Merge Sort
– O(n log n) comparison based sorting algorithm (best case, worst case, avg case)
– Produces a stable sort (implementation preserves the input order of equal elements in the sorted output)
– Top Down Implementation and Bottom Up Implementation
– Is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list
– Uses more memory (2n locations)
– Can be parallelized
2) Quick Sort
– Avg O(n log n) , Worst Case O(n ^ 2)
– Is comparison based sorting
– In place partioning algorithm and hence uses O(log n) additional space
– Can be parallelized (like mergesort)
– Depending on implementation may or may not be a stable sort
– Low memory required
– Useful in cases where data is in RAM, not useful in cases where data lives on disk (In that case use merge sort)
– usually faster than mergesort
– 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
QuickSort is more popular than Merge Sort because it:
Is in-place (MergeSort requires tons of extra memory).
Has a small hidden constant
3) Heap Sort
– Heapsort is part of the selection sort family. Is a comparison based sorting algo.
– it has the advantage of a more favorable worst-case O(n log n) runtime
– Heapsort is an in-place algorithm, but it is not a stable sort
– Quicksort is typically faster than Heapsort, 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
– Merge sort requires ?(n) auxiliary space, but heapsort requires only a constant amount.
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.
4) Intro Sort