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.