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.

Practice

1. What is the main idea behind the Quick Sort algorithm as a divide and conquer method?

easy

A. Sort elements by counting their frequency

B. Sort the array by repeatedly swapping adjacent elements

C. Use extra space to merge two sorted arrays

D. Divide the array into smaller parts, sort them, and combine results

Solution

1. Step 1: Understand divide and conquer in Quick Sort

   Quick Sort divides the array into smaller parts using a pivot, sorts each part, and combines results.

2. Step 2: Compare with other sorting methods

   Unlike bubble sort or counting sort, Quick Sort uses division and conquering subproblems.

3. Final Answer:

   Divide the array into smaller parts, sort them, and combine results -> Option D

4. Quick Check:

   Quick Sort = Divide and conquer [OK]

Hint: Remember: divide, sort parts, then combine [OK]

Common Mistakes:

• Confusing Quick Sort with bubble sort
• Thinking Quick Sort merges arrays like merge sort
• Believing Quick Sort counts frequencies

2. Which of the following is the correct TypeScript function signature for a Quick Sort function that sorts an array of numbers?

easy

A. function quickSort(arr: number[]): number[]

B. function quickSort(arr: string): string

C. function quickSort(arr: number): void

D. function quickSort(arr: any): any

Solution

1. Step 1: Identify correct parameter and return types

   The function takes an array of numbers and returns a sorted array of numbers.

2. Step 2: Check each option's signature

   function quickSort(arr: number[]): number[] matches input and output types correctly for Quick Sort.

3. Final Answer:

   function quickSort(arr: number[]): number[] -> Option A

4. Quick Check:

   Correct function signature = function quickSort(arr: number[]): number[] [OK]

Hint: Input and output types must match array of numbers [OK]

Common Mistakes:

• Using string instead of number array
• Returning void instead of sorted array
• Using any type without specificity

3. What will be the output of the following TypeScript Quick Sort call?

const arr = [3, 1, 4, 1];
console.log(quickSort(arr));

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length - 1];
  const left = arr.filter(x => x < pivot);
  const right = arr.filter(x => x > pivot);
  const equal = arr.filter(x => x === pivot);
  return [...quickSort(left), ...equal, ...quickSort(right)];
}

medium

A. [3, 1, 1, 4]

B. [1, 1, 3, 4]

C. [1, 3, 4, 1]

D. [4, 3, 1, 1]

Solution

1. Step 1: Understand pivot and partition

   Pivot is 1 (last element). Left = elements less than 1 (none), equal = [1,1], right = [3,4].

2. Step 2: Recursively sort left and right

   Left is empty, so returns []. Right is [3,4], pivot 4, left=[3], equal=[4], right=[]; sorted right = [3,4].

3. Final Answer:

   [1, 1, 3, 4] -> Option B

4. Quick Check:

   Sorted array = [1, 1, 3, 4] [OK]

Hint: Pivot last element, filter left, equal, right, then combine [OK]

Common Mistakes:

• Not including equal elements correctly
• Misplacing pivot in final array
• Confusing filter conditions

4. Identify the bug in this Quick Sort implementation and choose the fix:

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const pivot = arr[0];
  const left = arr.filter(x => x < pivot);
  const right = arr.filter(x => x > pivot);
  return [...quickSort(left), pivot, ...quickSort(right)];
}

medium

A. Change pivot to arr[arr.length - 1]

B. Return arr without recursion

C. Include elements equal to pivot in the result

D. Use arr.slice(1) for left and right filtering

Solution

1. Step 1: Analyze pivot handling and filtering

   Pivot is arr[0], but elements equal to pivot are excluded from left and right filters, causing missing elements.

2. Step 2: Fix by including equal elements

   We must include elements equal to pivot separately to avoid losing duplicates.

3. Final Answer:

   Include elements equal to pivot in the result -> Option C

4. Quick Check:

   Equal elements must be included [OK]

Hint: Remember to handle elements equal to pivot separately [OK]

Common Mistakes:

• Ignoring equal elements causes missing values
• Changing pivot position without fixing equal elements
• Not using recursion properly

5. Given an array with many duplicate values, which Quick Sort modification improves performance and correctness?

const arr = [5, 3, 5, 2, 5, 1, 5];

hard

A. Use three-way partitioning to separate less, equal, and greater elements

B. Always pick the first element as pivot without handling duplicates

C. Sort only unique elements and ignore duplicates

D. Use bubble sort instead for duplicates

Solution

1. Step 1: Understand problem with duplicates in Quick Sort

   Standard Quick Sort can degrade with many duplicates if equal elements are not handled well.

2. Step 2: Apply three-way partitioning

   Three-way partitioning divides array into less than, equal to, and greater than pivot, improving speed and correctness.

3. Final Answer:

   Use three-way partitioning to separate less, equal, and greater elements -> Option A

4. Quick Check:

   Three-way partitioning handles duplicates best [OK]

Hint: Use three-way partitioning for arrays with many duplicates [OK]

Common Mistakes:

• Ignoring duplicates causes slow sorting
• Picking pivot without handling equals
• Switching to bubble sort unnecessarily