Skip to main content

Sorting Algorithms

Learn about different sorting algorithms, their time and space complexity, and when to use each one.

Comparison-based Sorts​

Merge Sort​

  • Time Complexity: O(n log n) in all cases
  • Space Complexity: O(n)
  • Stability: Stable
  • In-place: No
  • Best for: When stability is required and extra space is available

Quick Sort​

  • Time Complexity: O(n log n) average, O(n²) worst case
  • Space Complexity: O(log n) average, O(n) worst case
  • Stability: Not stable
  • In-place: Yes (with proper implementation)
  • Best for: General-purpose sorting when average performance matters

Heap Sort​

  • Time Complexity: O(n log n) in all cases
  • Space Complexity: O(1)
  • Stability: Not stable
  • In-place: Yes
  • Best for: When O(1) space is required and stability is not needed

Non-comparison Sorts​

Counting Sort​

  • Time Complexity: O(n + k) where k is the range of input
  • Space Complexity: O(k)
  • Stability: Stable
  • In-place: No
  • Best for: When the range of input values is small

Radix Sort​

  • Time Complexity: O(d × (n + k)) where d is the number of digits
  • Space Complexity: O(n + k)
  • Stability: Stable
  • In-place: No
  • Best for: Sorting integers with a fixed number of digits

Bucket Sort​

  • Time Complexity: O(n + k) average case
  • Space Complexity: O(n + k)
  • Stability: Stable
  • In-place: No
  • Best for: When input is uniformly distributed over a range

Properties​

Stability​

A sorting algorithm is stable if it maintains the relative order of equal elements.

In-place​

An algorithm is in-place if it uses only a constant amount of extra memory.

When to Use Which Sort​

  • General purpose: Quick Sort or Merge Sort
  • Memory constrained: Heap Sort
  • Stability required: Merge Sort or Counting Sort
  • Small range of values: Counting Sort
  • Integer sorting: Radix Sort
  • Uniformly distributed data: Bucket Sort

Implementation Tips​

  1. Choose the right algorithm based on your constraints
  2. Consider the data characteristics (size, distribution, range)
  3. Optimize for your use case (time vs space vs stability)
  4. Test with real data to validate performance assumptions