Sorting Algorithms for DSA: Complete Guide

Recognition Cheat Sheet

If you see…	Think…
Sort an array	Built-in sort
Sort + pair/triplet	Sort + Two Pointers
In-place + O(n log n)	Heap Sort / Quick Sort
Stable + O(n log n)	Merge Sort
Kth element	Quickselect / Heap
Small value range	Counting Sort
Small / nearly sorted	Insertion Sort

Main Trigger

First ask: Do I actually need the whole array sorted?

1. Built-in Sorting

Same numbers, two sorters — see why JavaScript needs the numeric comparator.

Built-in Sort & the JS String Pitfall

A reminder that language built-ins need care: JavaScript's default .sort() compares values as STRINGS, so [10,9,1] sorts wrong. Always pass a numeric comparator (a,b) => a-b.

[10,9,1]: a naive .sort() compares '10' vs '9' lexically ('1' < '9') → [9,10,1], wrong. Adding (a,b)=>a-b compares numerically → [1,9,10]. Rule: primitives get a numeric comparator; objects get one on the key you need.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        nums.sort((a, b) => a - b)   // ALWAYS pass a numeric comparator
                      
                        2
                        // without it: JS compares STRINGS → '10' < '9' lexically

Arrays.sort(nums);

// objects with a custom comparator:
Arrays.sort(arr, (a, b) -> a.value - b.value);

nums.sort()                       # in place
arr.sort(key=lambda x: x.value)

std::sort(nums.begin(), nums.end());

// custom comparator:
std::sort(arr.begin(), arr.end(),
          [](const Item& a, const Item& b) {
              return a.value < b.value;
          });

nums.sort((a, b) => a - b); // numbers need the comparator!

arr.sort((a, b) => a.value - b.value);

Recognition

Need the array sorted → built-in sort

2. Sort + Two Pointers

After one sort, finding a target pair is just two pointers walking toward each other.

Sort + Two Pointers (Pair Sum)

Find a pair in an array that sums to a target. Sorting turns 'search for a partner for each element' into one O(n) converging walk: compare the two ends, then move the end that can fix an overshoot.

[4,2,7,1,5] sorted → [1,2,4,5,7], target 6. Pointers L (smallest) and R (largest) bracket every possible pair. 1+7=8 > 6 ⇒ R--; then 1+5=6 ⇒ found. If L tiny and even R isn't small enough, no partner for L exists further left — sorting guarantees it. L/R pointer labels show each move.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        sort(nums)
                      
                        2
                        left = 0, right = n-1
                      
                        3
                        while left < right:
                      
                        4
                          sum = nums[left] + nums[right]
                      
                        5
                          if sum == target: found!
                      
                        6
                          if sum < target: left++   // need bigger
                      
                        7
                          if sum > target: right--  // need smaller

Many pair and triplet problems become easier after sorting.

Arrays.sort(nums);

int left = 0;
int right = nums.length - 1;

while (left < right) {
    int sum = nums[left] + nums[right];

    if (sum == target) {
        // found pair
        left++;
        right--;
    } else if (sum < target) {
        left++;
    } else {
        right--;
    }
}

nums.sort()

left, right = 0, len(nums) - 1
while left < right:
    s = nums[left] + nums[right]
    if s == target:
        ...          # found pair
        left += 1; right -= 1
    elif s < target:
        left += 1
    else:
        right -= 1

std::sort(nums.begin(), nums.end());

int left = 0, right = nums.size() - 1;
while (left < right) {
    int sum = nums[left] + nums[right];
    if (sum == target) { /* found */ left++; right--; }
    else if (sum < target) left++;
    else right--;
}

nums.sort((a, b) => a - b);

let left = 0,
  right = nums.length - 1;
while (left < right) {
  const sum = nums[left] + nums[right];
  if (sum === target) {
    // found pair
    left++;
    right--;
  } else if (sum < target) {
    left++;
  } else {
    right--;
  }
}

Common problems:

Two Sum II
3Sum
Closest Pair
Pair with target sum

Recognition

Pair/triplet + sorted array → Two Pointers

3. Heap Sort

Max always bubbles to the front, then jumps to the sorted zone — watch the shaded region grow.

Heap Sort

Sort by first building a max-heap (every parent ≥ children), then repeatedly swapping the max (root) to the back of the array and sifting the new root down. The sorted region grows from the right; the remaining heap shrinks from the left.

Heap sort on [4,10,3,5,1]. Build phase sifts down to form the max-heap [10,5,3,4,1]; then each step swaps the root to the back and heapifies the shrunk heap, so the largest remaining element lands in its final spot. Watch the array reorder step by step.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        build max-heap: heapify(n/2-1 … 0)
                      
                        2
                        for end = n-1 … 1:
                      
                        3
                          swap(nums[0], nums[end])   // max → sorted zone
                      
                        4
                          heapify(nums, 0, end)      // fix the shrunk heap

Use Heap Sort when you need in-place O(n log n) sorting.

public void heapSort(int[] nums) {
    int n = nums.length;

    // Build max-heap
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(nums, n, i);

    // Move largest to the end
    for (int i = n - 1; i > 0; i--) {
        swap(nums, 0, i);
        heapify(nums, i, 0);
    }
}

private void heapify(int[] nums, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && nums[left] > nums[largest])
        largest = left;

    if (right < n && nums[right] > nums[largest])
        largest = right;

    if (largest != i) {
        swap(nums, i, largest);
        heapify(nums, n, largest);
    }
}

private void swap(int[] nums, int i, int j) {
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

def heap_sort(nums):
    import heapq

    h = [-x for x in nums]   # max-heap via negation
    heapq.heapify(h)

    for i in reversed(range(len(nums))):
        nums[i] = -heapq.heappop(h)

#include <algorithm>

void heapSort(std::vector<int>& nums) {
    std::make_heap(nums.begin(), nums.end());       // max-heap
    for (auto it = nums.end(); it != nums.begin(); --it)
        std::pop_heap(nums.begin(), it);            // max -> it-1
}

function heapSort(nums) {
  const n = nums.length;

  const heapify = (i, size) => {
    let largest = i;
    const l = 2 * i + 1,
      r = 2 * i + 2;
    if (l < size && nums[l] > nums[largest]) largest = l;
    if (r < size && nums[r] > nums[largest]) largest = r;
    if (largest !== i) {
      [nums[i], nums[largest]] = [nums[largest], nums[i]];
      heapify(largest, size);
    }
  };

  for (let i = (n >> 1) - 1; i >= 0; i--) heapify(i, n);
  for (let i = n - 1; i > 0; i--) {
    [nums[0], nums[i]] = [nums[i], nums[0]];
    heapify(0, i);
  }
}

Recognition

In-place + O(n log n) → Heap Sort

4. Merge Sort

Split to singletons, then merge upward — each merge writes values back in order.

Merge Sort

Given an unsorted array, sort it using merge sort?

Walk through the divide-and-conquer: split until singletons, then merge sorted halves by repeatedly taking the smaller head. On the input, split [38,27|43,10] -> four singletons -> merge pairs [27,38] and [10,43] -> final merge compares heads: 27 vs 10 -> 10, 27 vs 43 -> 27, 38 vs 43 -> 38, leftover 43. Merging two sorted runs is the only real work -- stable, guaranteed O(n log n). Uses O(n) auxiliary space.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        mergeSort(half): if len<=1 return
                      
                        2
                        split at mid; sort both halves
                      
                        3
                        merge: take smaller head into output

Merge Sort is useful when you need:

Guaranteed O(n log n)
Stable sorting
Divide and conquer

public void mergeSort(int[] nums) {
    if (nums.length <= 1)
        return;

    int mid = nums.length / 2;

    int[] left = Arrays.copyOfRange(nums, 0, mid);
    int[] right = Arrays.copyOfRange(nums, mid, nums.length);

    mergeSort(left);
    mergeSort(right);

    merge(nums, left, right);
}

private void merge(int[] nums, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;

    while (i < left.length && j < right.length) {
        if (left[i] <= right[j])
            nums[k++] = left[i++];
        else
            nums[k++] = right[j++];
    }

    while (i < left.length)
        nums[k++] = left[i++];

    while (j < right.length)
        nums[k++] = right[j++];
}

def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left, right = merge_sort(nums[:mid]), merge_sort(nums[mid:])

    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    return out + left[i:] + right[j:]

void mergeSort(vector<int>& nums) {
    if (nums.size() <= 1) return;
    int mid = nums.size() / 2;
    vector<int> L(nums.begin(), nums.begin() + mid),
                R(nums.begin() + mid, nums.end());
    mergeSort(L); mergeSort(R);

    size_t i = 0, j = 0, k = 0;
    while (i < L.size() && j < R.size())
        nums[k++] = (L[i] <= R[j]) ? L[i++] : R[j++];
    while (i < L.size()) nums[k++] = L[i++];
    while (j < R.size()) nums[k++] = R[j++];
}

function mergeSort(nums) {
  if (nums.length <= 1) return nums;
  const mid = nums.length >> 1;
  const left = mergeSort(nums.slice(0, mid));
  const right = mergeSort(nums.slice(mid));

  const out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length)
    out.push(left[i] <= right[j] ? left[i++] : right[j++]);
  return [...out, ...left.slice(i), ...right.slice(j)];
}

Recognition

Stable + guaranteed O(n log n) → Merge Sort

5. Quick Sort

Every pivot lands at its final home the moment its partition ends.

Quick Sort (Lomuto Partition)

Pick a pivot (here the last element), partition so everything smaller is left of it and everything larger is right, put the pivot in its final home, then recurse on the two sides. Average O(n log n).

Quicksort on [7,2,1,8,6], pivot=6. Lomuto: scan with j, swap smaller elements into the 'small zone' (i). After the scan, swap pivot 6 with nums[i]=7 → 6 is final. Recurse left [2,1] and right [8,7]. Shaded regions mark the zones; each pivot lands exactly where it belongs → [1,2,6,7,8].

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        quickSort(low, high): if low >= high return
                      
                        2
                        pivot = nums[high]; i = low
                      
                        3
                        for j in low..high-1:
                      
                        4
                          if nums[j] < pivot: swap(i, j); i++
                      
                        5
                        swap(i, high)               // pivot to its final home
                      
                        6
                        recurse on (low..i-1) and (i+1..high)

Quick Sort partitions the array around a pivot.

Choose pivot
    ↓
Partition
    ↓
Smaller | Pivot | Larger
    ↓
Repeat

public void quickSort(int[] nums, int low, int high) {
    if (low >= high)
        return;

    int pivot = partition(nums, low, high);

    quickSort(nums, low, pivot - 1);
    quickSort(nums, pivot + 1, high);
}

private int partition(int[] nums, int low, int high) {
    int pivot = nums[high];
    int i = low;

    for (int j = low; j < high; j++) {
        if (nums[j] < pivot) {
            swap(nums, i, j);
            i++;
        }
    }

    swap(nums, i, high);
    return i;
}

def quick_sort(nums, low=0, high=None):
    if high is None:
        high = len(nums) - 1
    if low >= high:
        return

    p = partition(nums, low, high)
    quick_sort(nums, low, p - 1)
    quick_sort(nums, p + 1, high)

def partition(nums, low, high):
    pivot, i = nums[high], low
    for j in range(low, high):
        if nums[j] < pivot:
            nums[i], nums[j] = nums[j], nums[i]
            i += 1
    nums[i], nums[high] = nums[high], nums[i]
    return i

void quickSort(vector<int>& nums, int low, int high) {
    if (low >= high) return;
    int p = partition(nums, low, high);
    quickSort(nums, low, p - 1);
    quickSort(nums, p + 1, high);
}

int partition(vector<int>& nums, int low, int high) {
    int pivot = nums[high], i = low;
    for (int j = low; j < high; j++)
        if (nums[j] < pivot)
            std::swap(nums[i++], nums[j]);
    std::swap(nums[i], nums[high]);
    return i;
}

function quickSort(nums, low = 0, high = nums.length - 1) {
  if (low >= high) return;
  const p = partition(nums, low, high);
  quickSort(nums, low, p - 1);
  quickSort(nums, p + 1, high);
}

function partition(nums, low, high) {
  const pivot = nums[high];
  let i = low;
  for (let j = low; j < high; j++) {
    if (nums[j] < pivot) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
    }
  }
  [nums[i], nums[high]] = [nums[high], nums[i]];
  return i;
}

Call it as quickSort(nums, 0, nums.length - 1).

Average: O(n log n). Worst case: O(n²).

6. Quickselect

One partition is enough — the pivot landing exactly on the target index answers k=3 instantly.

Quickselect (k-th Smallest)

Find the k-th smallest element WITHOUT sorting the whole array. Partition once; if the pivot lands exactly on the target index, you're done. Otherwise recurse into only the side that contains the target.

Quickselect for the 3rd smallest (target index 2) in [7,2,1,8,6]. Partition with pivot 6 → [2,1,6,8,7]; the pivot lands at index 2, which equals the target, so STOP — answer 6. Quicksort would recurse both halves; quickselect keeps just one, giving O(n) average.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        target = k-1; lo = 0; hi = n-1
                      
                        2
                        loop:
                      
                        3
                          p = partition(lo, hi)     // same as quicksort's
                      
                        4
                          if p == target: return nums[p]
                      
                        5
                          else narrow to the side containing target

If you only need the Kth smallest/largest, don’t sort the entire array.

public int quickSelect(int[] nums, int k) {
    int target = k - 1;
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int pivot = partition(nums, left, right);

        if (pivot == target)
            return nums[pivot];

        if (pivot < target)
            left = pivot + 1;
        else
            right = pivot - 1;
    }

    return -1;
}

def quick_select(nums, k):
    target, left, right = k - 1, 0, len(nums) - 1
    while left <= right:
        p = partition(nums, left, right)
        if p == target:
            return nums[p]
        if p < target:
            left = p + 1
        else:
            right = p - 1
    return -1

int quickSelect(vector<int>& nums, int k) {
    int target = k - 1, left = 0, right = nums.size() - 1;
    while (left <= right) {
        int p = partition(nums, left, right);
        if (p == target) return nums[p];
        if (p < target) left = p + 1;
        else right = p - 1;
    }
    return -1;
}

function quickSelect(nums, k) {
  const target = k - 1;
  let left = 0,
    right = nums.length - 1;
  while (left <= right) {
    const p = partition(nums, left, right); // from quick sort
    if (p === target) return nums[p];
    if (p < target) left = p + 1;
    else right = p - 1;
  }
  return -1;
}

Average: O(n).

Recognition

Kth element + don’t need full sorting → Quickselect

7. Counting Sort

Tally the frequencies, replay them in order — zero comparisons anywhere.

Counting Sort

When values are small integers, skip comparisons entirely: tally frequencies, then replay them in value order to rewrite the array. O(n + k) time where k is the value range.

Counting sort on [4,2,2,8,3,3,1] (range 1..8). Tally → counts {1:1, 2:2, 3:2, 4:1, 8:1}. Then write 1 once, 2 twice, 3 twice, 4 once, 8 once. Watch the array fill left to right from the counts. Trade-off: memory grows with the value range k.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        count[v]++ for every v            // tally 1..k
                      
                        2
                        read counts in order:
                      
                        3
                          while count[v] > 0:
                      
                        4
                            write v back; count[v]--

Use Counting Sort when values come from a small range.

Example:

nums = [1, 3, 1, 2, 3, 1]

count:
1 → 3
2 → 1
3 → 2

public void countingSort(int[] nums) {
    int max = 0;

    for (int num : nums)
        max = Math.max(max, num);

    int[] count = new int[max + 1];

    for (int num : nums)
        count[num]++;

    int index = 0;

    for (int value = 0; value < count.length; value++) {
        while (count[value]-- > 0)
            nums[index++] = value;
    }
}

def counting_sort(nums):
    count = [0] * (max(nums) + 1)
    for num in nums:
        count[num] += 1

    out = []
    for value, c in enumerate(count):
        out.extend([value] * c)
    return out

void countingSort(vector<int>& nums) {
    int mx = *max_element(nums.begin(), nums.end());
    vector<int> count(mx + 1, 0);
    for (int x : nums) count[x]++;

    int idx = 0;
    for (int v = 0; v < (int)count.size(); v++)
        while (count[v]-- > 0) nums[idx++] = v;
}

function countingSort(nums) {
  const max = Math.max(...nums);
  const count = new Array(max + 1).fill(0);
  for (const x of nums) count[x]++;

  let index = 0;
  for (let value = 0; value < count.length; value++)
    while (count[value]-- > 0) nums[index++] = value;
}

Time: O(n + range).

Recognition

Small value range → Counting Sort

8. Insertion Sort

A sorted prefix grows one card at a time; bigger neighbours shift right to make room.

Insertion Sort

Grow a sorted prefix one element at a time: lift the next value (key), shift every larger neighbour right to open a hole, then drop the key in. Like sorting a hand of cards.

Insertion sort on [5,3,4,1,2]. Take key=3, shift 5 right, drop 3 → [3,5]. key=4 shifts only 5 → [3,4,5]. key=1 shifts all three → drops at front. key=2 shifts 5,4,3 → [1,2,3,4,5]. When the array is nearly sorted, few shifts happen — that's its O(n) best case.

ARRAY VISUALIZER

Steps –

Press ▶ to animate, or step through manually.

Variables

keys: ← → space F

Pseudocode


                        1
                        for i in 1..n-1:
                      
                        2
                          key = nums[i]
                      
                        3
                          j = i-1
                      
                        4
                          while j >= 0 and nums[j] > key:
                      
                        5
                            nums[j+1] = nums[j]   // shift right
                      
                        6
                            j--
                      
                        7
                          nums[j+1] = key         // drop into place

Useful for small or nearly sorted arrays.

public void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {
        int current = nums[i];
        int j = i - 1;

        while (j >= 0 && nums[j] > current) {
            nums[j + 1] = nums[j];
            j--;
        }

        nums[j + 1] = current;
    }
}

def insertion_sort(nums):
    for i in range(1, len(nums)):
        current, j = nums[i], i - 1
        while j >= 0 and nums[j] > current:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = current

void insertionSort(vector<int>& nums) {
    for (int i = 1; i < (int)nums.size(); i++) {
        int current = nums[i], j = i - 1;
        while (j >= 0 && nums[j] > current)
            nums[j-- + 1] = nums[j];
        nums[j + 1] = current;
    }
}

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

Pattern:

Take next element
      ↓
Move larger elements right
      ↓
Insert element

Recognition

Small / nearly sorted → Insertion Sort

Common Mistakes

Sorting when you don’t need to

If the problem asks for:

Kth largest
Top K
K closest

you may only need:

Heap or Quickselect

Don’t automatically sort the entire array.

Ignoring space requirements

If the problem requires:

O(1) extra space

be careful with Merge Sort because the standard implementation uses an extra array.

Ignoring stability

If equal elements must keep their original order:

Stable sort → Merge Sort

JavaScript sort pitfall

nums.sort() compares STRINGS — [10,9,1] sorts to [1,10,9]. Always pass (a, b) => a - b.

Pattern Summary

Need normal sorting
→ built-in sort

Sort + pair/triplet
→ Sort + Two Pointers

In-place + O(n log n)
→ Heap Sort / Quick Sort

Stable + O(n log n)
→ Merge Sort

Kth element
→ Quickselect / Heap

Small value range
→ Counting Sort

Small / nearly sorted
→ Insertion Sort

Interview Rule

Don’t sort automatically. First identify what the problem actually needs.

If you need the whole array sorted, use a sorting algorithm.

If you only need K elements, pairs, triplets, or a specific ordering, another pattern may be better.

Earn Premium with Referrals

Recognition Cheat Sheet

Main Trigger

1. Built-in Sorting

Built-in Sort & the JS String Pitfall

Recognition

2. Sort + Two Pointers

Sort + Two Pointers (Pair Sum)

Recognition

3. Heap Sort

Heap Sort

Recognition

4. Merge Sort

Merge Sort

Recognition

5. Quick Sort

Quick Sort (Lomuto Partition)

6. Quickselect

Quickselect (k-th Smallest)

Recognition

7. Counting Sort

Counting Sort

Recognition

8. Insertion Sort

Insertion Sort

Recognition

Common Mistakes

Sorting when you don’t need to

Ignoring space requirements

Ignoring stability

JavaScript sort pitfall

Pattern Summary

Interview Rule

Premium Content

My Private Notes