Interview OS
Back to Algorithms & Data Structures

Library

Sorting algorithms

Merge, quick, heap, counting.

Divide & conquer

Overview

Sorting arranges data to unlock binary search, deduplication, and sweep techniques. This topic compares the classic algorithms by time, space, and stability so you can justify your choice and recognize when a problem needs sorting first.

How it works

Divide & conquer
InputDivideMergeOutputUnorderedn itemsSplitO(n log n)CombinepivotSorted
ClientServiceEdgeData

Step by step, with examples

  1. 1

    Unordered

    • Decide if you need stable or in-place.
  2. 2

    Split

    • Merge/quick split the input.
  3. 3

    Combine

    • Merge halves or partition on a pivot.
  4. 4

    Sorted

    • Emit ordered output.
    • Example: Timsort default

Overview

Comparison sorts (merge/quick/heap) are O(n log n); non-comparison sorts (counting/radix) can be O(n) on bounded keys.

When to use it

  • Pre-processing for two-pointer/greedy
  • Stable ordering needs (merge)
  • Bounded integer keys (counting)

Common pitfalls

  • Quicksort worst case on sorted input
  • Assuming sort stability when it isn't

Where this content comes from

For full transparency, this content is curated and verified from these sources:

CLRS — Introduction to AlgorithmsCurated competitive-programming archivesOppZen-authored algorithm guides