Overview

I was not able to find an easy-to-digest high-level summary of the popular sorting algorithms. This is my attempt to summarize the key pros and cons of the most widely used algorithms, including two popular hybrid sorts: Timsort and Introsort.

Quicksort

  • not stable
  • great best-case
  • good average-case
  • bad worst-case
  • O(log n) memory overhead

Very good general purpose sorting algorithm on average, except when stability or low memory overhead are vital.

Heapsort

  • not stable
  • good best/average/worst-case
  • O(1) memory overhead

Slower than Quicksort in best-case, but faster in worst-case. Much lower memory overhead than Quicksort. Use over Quicksort when bounded worst-case/memory overhead are important.

Merge sort

  • stable
  • good best/average/worst-case
  • O(n) memory overhead

Use over Quicksort/Heapsort when you need a stable sort. Has more memory overhead, but works very well for large datasets with only sequential access (e.g. magnetic tape). Merge sort is also highly parallelizable.

Insertion sort

  • stable
  • great best-case
  • bad average/worst-case
  • O(1) memory overhead

Best algorithm for small datasets or nearly sorted data, especially when stability is required (Quicksort is not stable).

Timsort (hybrid insertion/merge)

  • stable
  • great best-case
  • good average/best-case
  • O(n) memory overhead

Great stable sort. Combines the best case scenarios of Merge sort and Insertion sort. Better than Quicksort for nearly sorted data. Quicksort is faster and uses less memory for more complex datasets when stability is not a concern. More complex to implement.

Introsort (hybrid insertion/quicksort/heapsort)

  • not stable
  • good best/average/worst-case
  • O(log n) memory overhead

Great unstable sort. Uses the same small dataset insertion sort optimization as Timsort, but falls back on Quicksort/Heapsort instead of Merge sort, which means it's not a stable sorting algorithm. The purpose of the additional Heapsort fallback from Quicksort is to get the added benefit of Heapsort's worst-case O(n log n) rather than Quicksort's O(n^2). More complex to implement.