Merge Sort as Divide and Conquer in DSA Javascript

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 first dividing them into small piles, sorting each small pile, then carefully combining the piles back into one sorted stack.

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]

Sorted small parts:
[27, 38, 43] -> [3, 9, 10, 82]

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

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 list into two halves

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

Why: Divide the problem into smaller parts to make sorting easier

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

[38] and [27, 43]

Why: Keep dividing until each part has one or zero elements

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

[3, 9] and [82, 10]

Why: Divide the second half similarly for sorting

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

[27] and [43]

Why: Smallest parts ready to merge

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

[3] and [9]

Why: Smallest parts ready to merge

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

[82] and [10]

Why: Smallest parts ready to merge

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

[38] and [27, 43]

Why: Start merging sorted parts

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

[3, 9] and [82, 10]

Why: Merge small sorted parts

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

[3, 9] and [10, 82]

Why: Merge small sorted parts

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

[27, 38, 43]

Why: Merge sorted halves

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

[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 Javascript

class MergeSort {
  // Merge two sorted arrays into one sorted array
  static merge(left, right) {
    let result = [];
    let i = 0, j = 0;
    // Compare elements from left and right arrays
    while (i < left.length && j < right.length) {
      if (left[i] <= right[j]) {
        result.push(left[i]); // Add smaller or equal element from left
        i++;
      } else {
        result.push(right[j]); // Add smaller element from right
        j++;
      }
    }
    // Add remaining elements from left if any
    while (i < left.length) {
      result.push(left[i]);
      i++;
    }
    // Add remaining elements from right if any
    while (j < right.length) {
      result.push(right[j]);
      j++;
    }
    return result;
  }

  // Recursively split and merge the array
  static sort(arr) {
    if (arr.length <= 1) return arr; // Base case: single element is sorted
    const mid = Math.floor(arr.length / 2);
    // Split array into left and right halves
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    // Recursively sort left and right halves
    const sortedLeft = MergeSort.sort(left);
    const sortedRight = MergeSort.sort(right);
    // Merge sorted halves
    return MergeSort.merge(sortedLeft, sortedRight);
  }
}

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

if (arr.length <= 1) return arr;

stop splitting when array has one or zero elements

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

find middle index to split array

const left = arr.slice(0, mid);

create left half

const right = arr.slice(mid);

create right half

const sortedLeft = MergeSort.sort(left);

recursively sort left half

const sortedRight = MergeSort.sort(right);

recursively sort right half

while (i < left.length && j < right.length) { ... }

merge two sorted arrays by comparing elements

while (i < left.length) { ... }

append remaining elements from left if any

while (j < right.length) { ... }

append remaining elements from right if any

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 arrays are created during merging to hold sorted elements

vs Alternative: Compared to simple sorting like bubble sort (O(n²)), merge sort is much faster for large lists due to divide and conquer approach

Edge Cases

empty array

returns empty array immediately without error

DSA Javascript

if (arr.length <= 1) return arr;

array with one element

returns the single element array as is

DSA Javascript

if (arr.length <= 1) return arr;

array with duplicate elements

duplicates are preserved and sorted correctly

DSA Javascript

while (i < left.length && j < right.length) { ... }

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 arrays with length 0 or 1, causing infinite recursion
Fix: Add a base case check to return the array immediately if its length is 0 or 1

Mistake: Merging arrays without comparing elements properly, resulting in unsorted output
Fix: Use two pointers to compare elements from left and right arrays and merge in sorted order

Summary

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

Use it when you need an efficient, reliable sorting method for medium to large lists.

The key insight is dividing the problem into smaller pieces and conquering by merging sorted parts.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Select a pivot and partition the array around it

B. Sort the array by repeatedly swapping adjacent elements

C. Divide the array into halves, sort each half, then merge them

D. Insert elements one by one into a sorted list

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the array into two halves recursively until single elements remain.

2. Step 2: Merge sorted halves

   After splitting, it merges the halves back in sorted order to form the sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option C

4. Quick Check:

   Merge Sort = Divide and conquer with merging [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort uses a pivot like Quick Sort
• Believing Merge Sort sorts in place without merging

2. Which of the following is the correct base case check in a recursive Merge Sort function in JavaScript?

easy

A. if (array.length <= 1) return array;

B. if (array.length === 0) return null;

C. if (array.length > 1) return array;

D. if (array.length === 2) return array;

Solution

1. Step 1: Identify the stopping condition for recursion

   Merge Sort stops splitting when the array has 1 or 0 elements, as these are already sorted.

2. Step 2: Correct base case syntax

   The check if (array.length <= 1) return array; correctly returns the array when it can't be split further.

3. Final Answer:

   if (array.length <= 1) return array; -> Option A

4. Quick Check:

   Base case = array length ≤ 1 [OK]

Hint: Base case: array length 1 or less returns array [OK]

Common Mistakes:

• Returning null instead of the array
• Checking for length === 2 instead of ≤ 1
• Incorrectly returning array when length > 1

3. What will be the output of the following JavaScript code using Merge Sort?

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) {
  let result = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([4, 1, 3, 2]));

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Trace the recursive splitting

   The array [4,1,3,2] is split into [4,1] and [3,2], then further into single elements.

2. Step 2: Merge sorted halves step-by-step

   Merge [4] and [1] to get [1,4], merge [3] and [2] to get [2,3], then merge [1,4] and [2,3] to get [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

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

Hint: Merge halves in sorted order to get final sorted array [OK]

Common Mistakes:

• Confusing merge order and returning unsorted halves
• Forgetting to merge remaining elements after loop
• Incorrect slicing causing wrong splits

4. Identify the bug in this Merge Sort implementation snippet:

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) {
  let result = [];
  let i = 0, j = 0;
  while (i < left.length || j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }
  return result;
}

medium

A. The base case condition is incorrect

B. The while loop condition should use && instead of ||

C. The merge function does not return the result

D. The mid calculation is wrong

Solution

1. Step 1: Analyze the merge loop condition

   The loop uses while (i < left.length || j < right.length), which can cause accessing undefined elements.

2. Step 2: Correct loop condition for safe merging

   It should be while (i < left.length && j < right.length) to compare valid elements, then append leftovers after the loop.

3. Final Answer:

   The while loop condition should use && instead of || -> Option B

4. Quick Check:

   Use && in merge loop condition [OK]

Hint: Use && to avoid undefined element access in merge loop [OK]

Common Mistakes:

• Using || causes runtime errors accessing undefined
• Not appending leftover elements after loop
• Ignoring base case correctness

5. Given an array with many duplicate values, how can you modify the merge step in Merge Sort to ensure stable sorting (preserving original order of equal elements)?

hard

A. Randomly pick from left or right when elements are equal

B. When elements are equal, always take the element from the right array first

C. Skip equal elements during merge to avoid duplicates

D. When elements are equal, always take the element from the left array first

Solution

1. Step 1: Understand stable sorting in merge

   Stable sorting means equal elements keep their original order after sorting.

2. Step 2: Modify merge to preserve order

   When left[i] equals right[j], choose left[i] first to keep its original position before right[j].

3. Final Answer:

   When elements are equal, always take the element from the left array first -> Option D

4. Quick Check:

   Stable merge = pick left element first on ties [OK]

Hint: Pick left element first when equal to keep order stable [OK]

Common Mistakes:

• Picking right element first breaks stability
• Skipping duplicates loses data
• Random choice causes unstable sort