Sorting Algorithms

Organize collections so downstream algorithms—search, aggregation, compression—run dramatically faster.

What is it?

Sorting is the unsung hero of performant systems. Simple techniques such as bubble and insertion sort are easy to teach and shine on nearly sorted or very small inputs. Divide-and-conquer approaches like merge sort and quicksort scale to millions of records, while heapsort guarantees O(n log n) worst-case time with minimal extra memory. When keys come from a bounded range (timestamps, ZIP codes), counting or radix sort can beat the comparison lower bound altogether. Real products blend these ideas: language runtimes switch from quicksort to insertion sort for tiny partitions, analytics teams bucket events before merging, and distributed jobs perform external merge sort to handle terabytes that can’t fit in RAM. Once data is sorted, binary search, deduplication, and even compression become dramatically simpler.

Time Complexity

AccessN/A

SearchO(log n) after sorting

InsertionO(n log n) to re-sort

DeletionO(n log n) to re-sort

Implementation Example

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

mergeSort([5,3,8,4,2]);

Sorting Algorithms

Sorting Algorithms Deep Dive

Sorting is the gateway to fast analytics, search, and compression. Once data is sorted, caches behave better and downstream algorithms simplify.

?But why does this matter?

Real-world sorting implementations are hybrids—choosing between quicksort, mergesort, heapsort, or radix based on input size and characteristics.

Visual Flow

How it actually moves

Best case

O(n log n)

Most adaptive algorithms detect nearly sorted input to approach O(n).

Average case

O(n log n)

Balanced partitions keep recursion trees shallow.

Space usage

O(1) to O(n)

Quicksort sorts in-place; mergesort trades memory for stability.

Merge sort (top-down)

Split the array into halves until each half has 0 or 1 element.

Recursively sort each half.

Merge the halves by repeatedly taking the smaller front element from each list.

Continue merging until both halves are exhausted.

Merge sort stays O(n log n) even on adversarial input and remains stable.

Watch the best explainer

15 Sorting Algorithms in 6 Minutes

Timo Bingmann

The legendary 75M-view visualization — watch quicksort, mergesort, and radix race.

Organize a spice rack

If jars are in random order, every recipe is a treasure hunt. Once they are alphabetized (or grouped by cuisine), finding cumin takes seconds.

Real-world analogy

Analytics engineers sort events by timestamp before windowing so queries can roll through data sequentially.

Takeaway

Sorting is prep work that unlocks faster downstream processing and clearer mental models.

Practical applications

• Financial exchanges ordering trades by timestamp before settlement.
• Build systems topologically sorting dependency graphs.
• Analytics teams ranking metrics, feature flags, or experiment cohorts.

Technical insights

• Comparison sorts have a theoretical lower bound of O(n log n); counting/radix sorts beat this when key ranges are limited.
• Stable sorts preserve relative order and are critical for multi-key sorting (sort by city, then by name).
• External sorting pipelines (e.g., MapReduce) chunk, sort, and merge data that cannot fit in memory.

When to reach for it

• Before binary searching or deduplication steps.
• To improve compression ratios (sorted data deltas better).
• Any workflow that batches events by SLA or priority.

Operations Breakdown

Best case

O(n log n)

Most adaptive algorithms detect nearly sorted input to approach O(n).

Average case

O(n log n)

Balanced partitions keep recursion trees shallow.

Space usage

O(1) to O(n)

Quicksort sorts in-place; mergesort trades memory for stability.

Best practices

• Detect small partitions and switch to insertion sort—it outperforms on < 16 elements.
• Exploit domain knowledge (bucket items by month, region) before full comparison sort.
• Validate comparators are transitive and total; inconsistent comparators crash sort implementations.

Common pitfalls

• Naïve quicksort suffers from O(n²) on partially sorted data; always randomize or median-of-three.
• Allocating a fresh array per recursive call quickly exhausts memory.
• Ignoring locale/Unicode collation leads to incorrect alphabetical ordering for global audiences.

Every kind of Sorting Algorithms

Interviewers rarely say which flavor they mean — they expect you to recognize it from the problem. Each variant below comes with the algorithms it unlocks.

Type 1 of 5

Simple Quadratic Sorts

→ full page

Bubble, selection, and insertion sort. Insertion sort is the one that survives in production — as the small-array finisher inside faster sorts.

What to know

Insertion sort is O(n + inversions): nearly-sorted data sorts in near-linear time.
Selection sort makes the minimum number of swaps — relevant when writes are expensive.
Standard libraries switch to insertion sort below ~16–32 elements.

Algorithms to reach for

Insertion sort

O(n²), O(n) best

Small or nearly-sorted arrays, online insertion

Selection sort

O(n²)

Minimize swap count on write-costly media

In the wild: The base case inside quicksort/Timsort, sorting hands of cards, tiny embedded systems.

Practice problems — hints, approach & solution on their own pages

Insertion Sort ListMedium Sort an ArrayMedium

Type 2 of 5

Quicksort & Partitioning

→ full page

Partition around a pivot, recurse on both sides. Fastest comparison sort in practice thanks to cache behavior — and partitioning alone powers Quickselect.

What to know

Random or median-of-three pivots make the O(n²) worst case vanishingly rare.
Three-way (Dutch flag) partitioning handles massive duplicate runs in O(n).
Not stable; introsort falls back to heapsort past a depth limit to cap the worst case.
Quickselect finds the kth element in expected O(n) — no full sort needed.

Algorithms to reach for

Quicksort (Hoare/Lomuto)

O(n log n) avg

General in-place sorting

Quickselect

O(n) expected

Kth largest without sorting (LeetCode 215)

Three-way partition

O(n)

Sort with many duplicate keys

In the wild: C stdlib qsort, C++ std::sort core, median/percentile computations.

Practice problems — hints, approach & solution on their own pages

Kth Largest Element in an ArrayMedium Sort ColorsMedium Top K Frequent ElementsMedium

Type 3 of 5

Merge Sort & Stable Divide-and-Conquer

→ full page

Split, sort halves, merge. Guaranteed O(n log n), stable, and the only comparison sort that streams — which is why databases external-sort with it.

What to know

Stability preserves equal elements’ order — required for multi-key sorts.
The merge step counts inversions and "counts smaller after self" almost for free.
External merge sort: sort chunks that fit in RAM, then k-way merge runs from disk.
On linked lists, merge sort needs O(1) extra space — the list sort of choice.

Algorithms to reach for

Merge sort

O(n log n)

Stable guaranteed O(n log n)

Count inversions

O(n log n)

Measure disorder during merge

External k-way merge

O(n log n)

Sort data far larger than memory

In the wild: Database ORDER BY spills, log-file merging, MapReduce shuffle phase.

Practice problems — hints, approach & solution on their own pages

Sort ListMedium Merge IntervalsMedium Reverse PairsHard

Type 4 of 5

Heapsort & Hybrid Sorts (Timsort, Introsort)

→ full page

Heapsort gives worst-case O(n log n) in place; real libraries blend algorithms — Timsort (merge + insertion) and introsort (quick + heap + insertion).

What to know

Heapsort: build a max-heap in O(n), then repeatedly swap the root to the back.
Timsort detects natural runs and merges them with galloping — O(n) on sorted input.
Introsort switches quicksort → heapsort past 2·log n recursion depth.

Algorithms to reach for

Heapsort

O(n log n)

Guaranteed O(n log n), O(1) space, adversary-proof

Timsort

O(n) – O(n log n)

Exploit existing order in real-world data

Introsort

O(n log n)

Quicksort speed with a hard worst-case cap

In the wild: Python sorted()/list.sort, Java Arrays.sort(objects), C++ std::sort, V8 Array.sort.

Practice problems — hints, approach & solution on their own pages

Sort an ArrayMedium Wiggle Sort IIMedium

Type 5 of 5

Non-Comparison Sorts (Counting, Radix, Bucket)

→ full page

Beat the O(n log n) comparison lower bound by not comparing: count occurrences, sort digit by digit, or scatter into buckets.

What to know

Counting sort needs a bounded integer range k; O(n + k) time and space.
LSD radix sort applies a stable counting sort per digit — 32-bit ints in 4 byte-passes.
Bucket sort assumes roughly uniform distribution; each bucket insertion-sorts.

Algorithms to reach for

Counting sort

O(n + k)

Small-range integers (ages, grades, bytes)

Radix sort (LSD)

O(d · (n + b))

Fixed-width ints/strings without comparisons

Bucket sort

O(n) average

Uniformly distributed floats

In the wild: Suffix-array construction, GPU sorts, histogram binning, sorting network packets by port.

Practice problems — hints, approach & solution on their own pages

Maximum GapMedium H-IndexMedium Sort Characters By FrequencyMedium

Signature algorithms

Algorithm

Bubble sort

Repeatedly swap adjacent out-of-order elements. Great for teaching purposes and nearly sorted arrays.

Time

O(n²)

Space

O(1)

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i += 1) {
    for (let j = 0; j < a.length - i - 1; j += 1) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
      }
    }
  }
  return a;
}

Algorithm

Insertion sort

Build the sorted list one element at a time by inserting into the correct position. Fantastic for tiny slices.

Time

O(n²) worst, O(n) best

Space

O(1)

function insertionSort(arr) {
  const a = [...arr];
  for (let i = 1; i < a.length; i += 1) {
    const value = a[i];
    let j = i - 1;
    while (j >= 0 && a[j] > value) {
      a[j + 1] = a[j];
      j -= 1;
    }
    a[j + 1] = value;
  }
  return a;
}

Algorithm

Merge sort

Divide-and-conquer strategy that guarantees O(n log n) time and remains stable, at the cost of extra memory.

Time

O(n log n)

Space

O(n)

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

Algorithm

Quick sort

Partition around a pivot to place items smaller on the left and larger on the right. Average-case champ that sorts in-place.

Time

O(n log n) average

Space

O(log n)

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length >> 1];
  const left = [];
  const right = [];
  const equal = [];
  for (const value of arr) {
    if (value < pivot) left.push(value);
    else if (value > pivot) right.push(value);
    else equal.push(value);
  }
  return [...quickSort(left), ...equal, ...quickSort(right)];
}

Pseudo Code • Merge sort (top-down)

Flow Diagram

Split the array into halves until each half has 0 or 1 element.
Recursively sort each half.
Merge the halves by repeatedly taking the smaller front element from each list.
Continue merging until both halves are exhausted.

Merge sort stays O(n log n) even on adversarial input and remains stable.

Hands-on code

Compare how the same idea looks in JavaScript, Python, and Go.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

Language insights

JavaScript (V8)

Hybrid of insertion sort for small partitions and randomized quicksort/TimSort-style merges for larger arrays; stable since ES2019.

Average O(n log n), worst O(n log n) due to safeguards, space O(log n).

Python

Uses Timsort for list.sort() and sorted(), blending merge sort with insertion sort on naturally ordered runs.

O(n log n) time, O(n) auxiliary space, O(n) worst-case comparisons.

sort.Slice uses a hybrid introsort (quicksort + heapsort fallback) with insertion sort for small ranges.

Average O(n log n) time, O(log n) space due to recursion depth.

Related Data Structures

Searching Algorithms

Techniques that help you locate the right data point quickly—from linear scans to binary search and index-assisted lookups.

Arrays

A collection of items stored at contiguous memory locations. Elements can be accessed randomly using indices.

Hash Tables

A data structure that stores key-value pairs. It uses a hash function to compute an index into an array of buckets, from which the desired value can be found.

Sorting Algorithms

What is it?

Time Complexity

Implementation Example

Sorting Algorithms Deep Dive

How it actually moves

15 Sorting Algorithms in 6 Minutes

Organize a spice rack

Practical applications

Technical insights

When to reach for it

Related topics

Operations Breakdown

Best practices

Common pitfalls

Every kind of Sorting Algorithms

Simple Quadratic Sorts

Quicksort & Partitioning

Merge Sort & Stable Divide-and-Conquer

Heapsort & Hybrid Sorts (Timsort, Introsort)

Non-Comparison Sorts (Counting, Radix, Bucket)

Signature algorithms

Bubble sort

Insertion sort

Merge sort

Quick sort

Pseudo Code • Merge sort (top-down)

Hands-on code

Language insights

Related Data Structures