Quick Sort as Divide and Conquer in DSA Typescript

Mental Model

Quick Sort splits the list into smaller parts around a pivot, sorts each part, then combines them to get a sorted list.

Analogy: Imagine sorting a pile of cards by picking one card as a divider, putting smaller cards on one side and bigger cards on the other, then sorting each side separately.

Unsorted array:
[ 7, 2, 5, 3, 9 ]

Pivot chosen:
[ 7, 2, 5, 3, 9 ]
 ↑

Split into parts:
[ 2, 5, 3, 7 ] [ 9 ]

Sort parts recursively and combine:
[ 2, 3, 5, 7 ] [ 9 ]

Final sorted:
[ 2, 3, 5, 7, 9 ]

Dry Run Walkthrough

Input: array: [7, 2, 5, 3, 9]

Goal: Sort the array in ascending order using Quick Sort

Step 1: Choose pivot as last element 9, partition array around pivot

[7, 2, 5, 3, 9] (pivot=9)

Why: Pivot divides array into smaller and larger elements

Step 2: Partition: all elements less than 9 stay left, none greater, pivot placed at end

[7, 2, 5, 3, 9]

Why: All elements are less than pivot, so pivot stays at last position

Step 3: Recursively quick sort left part [7, 2, 5, 3]

[7, 2, 5, 3]

Why: Sort smaller part to get fully sorted array

Step 4: Choose pivot 3, partition around pivot

[7, 2, 5, 3] (pivot=3)

Why: Pivot divides subarray into smaller and larger elements

Step 5: Partition: move elements less than 3 to left, greater to right, place pivot

[2, 3, 5, 7]

Why: Pivot placed correctly, smaller elements left, larger right

Step 6: Recursively quick sort left part [2]

[2]

Why: Single element is already sorted

Step 7: Recursively quick sort right part [5, 7]

[5, 7]

Why: Sort remaining elements

Step 8: Choose pivot 7, partition [5, 7]

[5, 7] (pivot=7)

Why: Pivot divides subarray

Step 9: Partition done, array is sorted

[2, 3, 5, 7, 9]

Why: All parts sorted and combined

Result:

[2, 3, 5, 7, 9] - sorted array

Annotated Code

DSA Typescript

class QuickSort {
  static partition(arr: number[], low: number, high: number): number {
    const pivot = arr[high];
    let i = low - 1;
    for (let j = low; j < high; j++) {
      if (arr[j] < pivot) {
        i++;
        [arr[i], arr[j]] = [arr[j], arr[i]];
      }
    }
    [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
    return i + 1;
  }

  static quickSort(arr: number[], low: number, high: number): void {
    if (low < high) {
      const pi = this.partition(arr, low, high);
      this.quickSort(arr, low, pi - 1);
      this.quickSort(arr, pi + 1, high);
    }
  }
}

const arr = [7, 2, 5, 3, 9];
QuickSort.quickSort(arr, 0, arr.length - 1);
console.log(arr.join(", "));

const pivot = arr[high];

Select pivot as last element to divide array

for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap arr[i] and arr[j]; } }

Partition elements smaller than pivot to left side

swap arr[i + 1] and arr[high]; return i + 1;

Place pivot in correct position and return index

if (low < high) { quickSort left part; quickSort right part; }

Recursively sort subarrays around pivot

Output

2, 3, 5, 7, 9

Complexity Analysis

Time: O(n log n) average case because the array is divided roughly in half each time and all elements are processed during partition

Space: O(log n) due to recursion stack in average case

vs Alternative: Better than simple sorting like bubble sort O(n²) because it divides problem and conquers smaller parts efficiently

Edge Cases

Empty array

No sorting needed, function returns immediately

DSA Typescript

if (low < high) { ... }

Array with one element

Already sorted, recursion stops immediately

DSA Typescript

if (low < high) { ... }

Array with all equal elements

Partition keeps elements in place, recursion still works correctly

DSA Typescript

if (arr[j] < pivot) { ... }

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently by splitting into smaller parts, reach for Quick Sort because it uses divide and conquer to sort fast.

Common Mistakes

Mistake: Choosing pivot incorrectly or not swapping elements properly during partition
Fix: Always pick pivot as last element and swap elements smaller than pivot to left side carefully

Mistake: Not updating indices correctly during partition causing infinite loops or wrong sorting
Fix: Use separate pointers i and j and increment i only when swapping smaller elements

Summary

Quick Sort sorts an array by dividing it around a pivot and sorting parts recursively.

Use Quick Sort when you want an efficient average-case sorting algorithm with divide and conquer.

The key insight is partitioning the array around a pivot to reduce the problem size each step.