Merge Sort as Divide and Conquer in DSA Typescript

Mental Model

Split the list into smaller parts, sort each part, then join them back in order.

Analogy: Imagine sorting a big pile of cards by splitting them into small piles, sorting each small pile, then carefully merging the piles back together in order.

Original list:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]   [3, 9, 82, 10]

Split again:
[38] [27, 43]   [3, 9] [82, 10]

Split until single elements:
[38] [27] [43]   [3] [9] [82] [10]

Dry Run Walkthrough

Input: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split the list into two halves

[38, 27, 43]   [3, 9, 82, 10]

Why: Divide the problem into smaller parts to sort separately

Step 2: Split left half into [38] and [27, 43]

[38]   [27, 43]   [3, 9, 82, 10]

Why: Keep dividing until sublists have one element

Step 3: Split [27, 43] into [27] and [43]

[38]   [27]   [43]   [3, 9, 82, 10]

Why: Sublists with one element are sorted by definition

Step 4: Merge [27] and [43] into sorted [27, 43]

[38]   [27, 43]   [3, 9, 82, 10]

Why: Combine two sorted lists into one sorted list

Step 5: Merge [38] and [27, 43] into sorted [27, 38, 43]

[27, 38, 43]   [3, 9, 82, 10]

Why: Merge sorted sublists to build bigger sorted list

Step 6: Split right half into [3, 9] and [82, 10]

[27, 38, 43]   [3, 9]   [82, 10]

Why: Divide right half to sort smaller parts

Step 7: Split [3, 9] into [3] and [9]

[27, 38, 43]   [3]   [9]   [82, 10]

Why: Single elements are sorted

Step 8: Merge [3] and [9] into [3, 9]

[27, 38, 43]   [3, 9]   [82, 10]

Why: Merge sorted sublists

Step 9: Split [82, 10] into [82] and [10]

[27, 38, 43]   [3, 9]   [82]   [10]

Why: Divide until single elements

Step 10: Merge [82] and [10] into [10, 82]

[27, 38, 43]   [3, 9]   [10, 82]

Why: Merge sorted sublists

Step 11: Merge [3, 9] and [10, 82] into [3, 9, 10, 82]

[27, 38, 43]   [3, 9, 10, 82]

Why: Merge sorted halves

Step 12: Merge [27, 38, 43] and [3, 9, 10, 82] into fully sorted list

[3, 9, 10, 27, 38, 43, 82]

Why: Final merge to get fully sorted list

Result:

[3, 9, 10, 27, 38, 43, 82]

Annotated Code

DSA Typescript

class MergeSort {
  static merge(left: number[], right: number[]): number[] {
    const result: number[] = [];
    let i = 0, j = 0;
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        result.push(left[i]);
        i++; // advance i to pick next from left
      } else {
        result.push(right[j]);
        j++; // advance j to pick next from right
      }
    }
    // Append remaining elements
    while (i < left.length) {
      result.push(left[i]);
      i++; // add leftover from left
    }
    while (j < right.length) {
      result.push(right[j]);
      j++; // add leftover from right
    }
    return result;
  }

  static mergeSort(arr: number[]): number[] {
    if (arr.length <= 1) return arr; // base case: single element is sorted
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid); // split left half
    const right = arr.slice(mid);   // split right half
    const sortedLeft = MergeSort.mergeSort(left); // sort left recursively
    const sortedRight = MergeSort.mergeSort(right); // sort right recursively
    return MergeSort.merge(sortedLeft, sortedRight); // merge sorted halves
  }
}

// Driver code
const input = [38, 27, 43, 3, 9, 82, 10];
const sorted = MergeSort.mergeSort(input);
console.log(sorted.join(", ") + "\n");

if (arr.length <= 1) return arr; // base case: single element is sorted

stop splitting when sublist has one or zero elements

const mid = Math.floor(arr.length / 2);

find middle index to split list

const left = arr.slice(0, mid); // split left half const right = arr.slice(mid); // split right half

divide list into two halves

const sortedLeft = MergeSort.mergeSort(left); // sort left recursively const sortedRight = MergeSort.mergeSort(right); // sort right recursively

recursively sort each half

return MergeSort.merge(sortedLeft, sortedRight); // merge sorted halves

combine two sorted lists into one sorted list

while (i < left.length && j < right.length) { if (left[i] <= right[j]) { result.push(left[i]); i++; // advance i to pick next from left } else { result.push(right[j]); j++; // advance j to pick next from right } }

merge elements by comparing heads of left and right

while (i < left.length) { result.push(left[i]); i++; // add leftover from left } while (j < right.length) { result.push(right[j]); j++; // add leftover from right }

append remaining elements after one list is exhausted

Output

3, 9, 10, 27, 38, 43, 82

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because extra space is needed to hold merged lists during the process

vs Alternative: Compared to bubble sort's O(n²), merge sort is much faster for large lists due to divide and conquer splitting

Edge Cases

empty list

returns empty list immediately without error

DSA Typescript

if (arr.length <= 1) return arr; // base case: single element is sorted

single element list

returns the single element list as sorted

DSA Typescript

if (arr.length <= 1) return arr; // base case: single element is sorted

list with duplicate elements

duplicates are preserved and sorted correctly

DSA Typescript

if (left[i] <= right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; }

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently, especially large lists, reach for merge sort because it splits the problem into smaller parts and merges them back sorted.

Common Mistakes

Mistake: Not handling the base case of single element or empty list, causing infinite recursion
Fix: Add a base case to return the list immediately if its length is 0 or 1

Mistake: Merging without comparing elements properly, leading to unsorted output
Fix: Compare elements from left and right lists and pick the smaller one each time

Summary

It sorts a list by splitting it into smaller parts, sorting those, and merging them back.

Use it when you need a reliable, efficient sorting method for large or unsorted data.

The key insight is breaking the problem into smaller sorted pieces and merging them carefully.