Sorting Algorithms

How to sort elements in a list? What are the common sorting algorithms? Which sorting algorithm to use? How do they fare against each other?

Sorting Algorithm? Stable? In-Place?

Sorting Algorithms Comparison

NameBestAverageWorstMemoryStableMethodOther notes
Quicksortnlog(n)nlog(n)n^2log(n)NoPartitioningQuicksort is usually done in-place with O(log(n)) stack space.
Merge sortnlog(n)nlog(n)nlog(n)nYesMergingHighly parallelizable (up to O(log(n)) using the Three Hungarians’ Algorithm).
In-place merge sortn(log(n)^2)1YesMergingCan be implemented as a stable sort based on stable in-place merging.
Insertion sortnn^2n^21YesInsertionO(n + d), in the worst case over sequences that have d inversions.
Timsortnnlog(n)nlog(n)nYesInsertion & MergingMakes n comparisons when the data is already sorted or reverse sorted.
Selection sortn^2n^2n^21NoSelectionStable with O(n) extra space or when using linked lists.
Bubble sortnn^2n^21YesExchangingTiny code size.
Gnome sortnn^2n^21YesExchangingTiny code size.

Sorting Problems

  • Merge Overlapping Intervals
    • For example,
      let the given set of intervals be {{1,3}, {2,4}, {5,7}, {6,8}}. The intervals {1,3} and {2,4} overlap with each other, so they should be merged and become {1,4}. Similarly, {5,7} and {6,8} should be merged and become {5,8}
    • Solution:
      • Sort the intervals and then merge them in a linear fashion