Merge Sort Algorithm in DSA Javascript

Mental Model

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

Analogy: Imagine sorting a big pile of cards by splitting them into small piles, sorting each small pile, then carefully combining the piles back into one sorted stack.

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

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

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

Sorted and merged:
[27, 38, 43]   [3, 9, 10, 82]

Final 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]   [3, 9, 82, 10]

Why: Splitting makes sorting smaller parts easier

Step 2: Split left half into smaller parts

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

Why: Keep splitting until parts have one element

Step 3: Split right half into smaller parts

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

Why: Smaller parts are easier to sort

Step 4: Sort and merge [27, 43]

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

Why: Merge sorted parts to build bigger sorted parts

Step 5: Sort and merge [3, 9]

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

Why: Sort smaller parts before merging bigger parts

Step 6: Sort and merge [82, 10]

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

Why: Sort pairs to prepare for final merges

Step 7: Merge [3, 9] and [10, 82]

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

Why: Combine sorted parts into bigger sorted parts

Step 8: Merge [38] and [27, 43]

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

Why: Merge sorted left half

Step 9: Merge two halves into final sorted list

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

Why: Final merge produces fully sorted list

Result:

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

Annotated Code

DSA Javascript

class MergeSort {
  static 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++;
      }
    }
    // Append remaining elements
    while (i < left.length) {
      result.push(left[i]);
      i++;
    }
    while (j < right.length) {
      result.push(right[j]);
      j++;
    }
    return result;
  }

  static sort(arr) {
    if (arr.length <= 1) return arr;
    const mid = Math.floor(arr.length / 2);
    const left = arr.slice(0, mid);
    const right = arr.slice(mid);
    const sortedLeft = MergeSort.sort(left);
    const sortedRight = MergeSort.sort(right);
    return MergeSort.merge(sortedLeft, sortedRight);
  }
}

// Driver code
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 part 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) { if (left[i] < right[j]) { result.push(left[i]); i++; } else { result.push(right[j]); j++; } }

merge two sorted halves by comparing elements

while (i < left.length) { result.push(left[i]); i++; }

append remaining elements from left half

while (j < right.length) { result.push(right[j]); j++; }

append remaining elements from right half

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 merged (n operations per merge)

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

vs Alternative: Compared to simple sorting like bubble sort (O(n²)), merge sort is much faster for large lists but uses extra memory

Edge Cases

empty list

returns empty list immediately without error

DSA Javascript

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

single element list

returns the single element list as is

DSA Javascript

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

list with duplicate elements

duplicates are kept and sorted correctly

DSA Javascript

while (i < left.length && j < right.length) { if (left[i] < right[j]) { ... } else { ... } }

When to Use This Pattern

When you need to sort a list efficiently and can use extra space, reach for merge sort because it splits and merges to sort in O(n log n) time.

Common Mistakes

Mistake: Not handling the base case when the list has one or zero elements, causing infinite recursion
Fix: Add a base case to return the list immediately if its length is 1 or less

Mistake: Merging without comparing elements properly, leading to unsorted results
Fix: Compare elements from both halves and add the smaller one to the result each time

Mistake: Forgetting to append remaining elements after one half is exhausted
Fix: After the main merge loop, append any leftover elements from either half

Summary

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

Use it when you want a reliable, efficient sort that works well on large lists.

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

Practice

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

easy

A. Insert elements one by one into a sorted sublist

B. Sort the array by repeatedly swapping adjacent elements

C. Pick a pivot and partition the array around it

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

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

   It then merges these sorted halves back together to form a sorted array.

3. Final Answer:

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

4. Quick Check:

   Merge Sort = Divide, sort halves, merge [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 extra space

2. Which of the following is the correct way to split an array arr into two halves in JavaScript for Merge Sort?

easy

A. const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid);

B. const mid = arr.length / 2; const left = arr.splice(0, mid); const right = arr.splice(mid);

C. const mid = arr.length / 2; const left = arr.slice(mid); const right = arr.slice(0, mid);

D. const mid = Math.ceil(arr.length / 2); const left = arr.slice(mid); const right = arr.slice(0, mid);

Solution

1. Step 1: Calculate middle index correctly

   Use Math.floor to get the middle index for even or odd lengths.

2. Step 2: Use slice to split without modifying original array

   Slice(0, mid) gets left half; slice(mid) gets right half correctly.

3. Final Answer:

   const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid); -> Option A

4. Quick Check:

   Use Math.floor and slice for splitting [OK]

Hint: Use Math.floor and slice to split arrays safely [OK]

Common Mistakes:

• Using splice which modifies the original array
• Not flooring the middle index causing float errors
• Swapping left and right halves incorrectly

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

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

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Recursively split and sort the array

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

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

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

3. Final Answer:

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

4. Quick Check:

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

Hint: Trace splits and merges carefully to find sorted output [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Not handling empty arrays in merge
• Using shift inefficiently causing performance issues

4. Identify the bug in this Merge Sort implementation:

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

medium

A. Base case should be arr.length <= 1, not arr.length === 1

B. Using shift() inside merge causes infinite loop

C. Math.floor should be Math.ceil for mid calculation

D. merge function should return result.reverse()

Solution

1. Step 1: Check base case condition

   Base case returns when array length is 1, but it should also handle empty arrays (length 0) to avoid errors.

2. Step 2: Correct base case to include empty arrays

   Change condition to arr.length <= 1 to safely return arrays of length 0 or 1.

3. Final Answer:

   Base case should be arr.length <= 1, not arr.length === 1 -> Option A

4. Quick Check:

   Base case = arr.length <= 1 [OK]

Hint: Base case must handle empty arrays too [OK]

Common Mistakes:

• Ignoring empty array base case causing stack overflow
• Incorrect mid calculation causing wrong splits
• Misunderstanding shift() usage as a bug

5. You want to sort a large array of objects by a numeric property score using Merge Sort. Which modification is needed in the merge function to correctly sort by score?

hard

A. Use JSON.stringify to compare objects

B. Compare left[0].score and right[0].score instead of elements directly

C. Convert objects to strings before comparing

D. Sort only keys, then map back to objects

Solution

1. Step 1: Understand sorting objects by property

   Objects cannot be compared directly; comparison must use the numeric property score.

2. Step 2: Modify merge comparison to use score

   Change condition to compare left[0].score and right[0].score to merge correctly.

3. Final Answer:

   Compare left[0].score and right[0].score instead of elements directly -> Option B

4. Quick Check:

   Compare object properties for sorting [OK]

Hint: Compare object properties, not whole objects [OK]

Common Mistakes:

• Trying to compare objects directly causing NaN or errors
• Using string conversion which breaks numeric order
• Sorting keys separately losing object structure