Faster by Splitting and Merging: Merge Sort

Chris is feeling confident now. He was handling data quite efficiently with Insertion Sort.

Then one day, a request came from the company: "Sort 100,000 user logs by date."

Chris confidently ran Insertion Sort.

...1 second, 2 seconds, 10 seconds...

The browser froze again.

"Wait, I thought Insertion Sort was fast?"

"That's only when the data is nearly sorted! Running O(N^2) on 100,000 random items means 10 billion operations!"

Now we need to graduate from the "amateur league" of sorting and enter the pro league.

Regardless of how much data there is or how shuffled it is, we need the unwavering speed of O(N log N). The first runner in this category is the textbook definition of "Divide and Conquer": Merge Sort.

1. Divide and Conquer: "If it's hard, split it"

The idea behind Merge Sort is simple.

"Sorting 100,000 items is hard, but sorting 0 or 1 item is easy."

Let's take the array [8, 3, 5, 1] as an example.

2. Core Logic: Merging Two Sorted Arrays

To implement Merge Sort, we first need a helper function that "combines two already sorted arrays into one."

This process is like pointing with your fingers (pointers) at the front of two arrays and comparing them.

// Function to merge two sorted arrays (arr1, arr2)
function merge(arr1, arr2) {
  let results = [];
  let i = 0; // Pointer for arr1
  let j = 0; // Pointer for arr2

  // While there are elements to compare in both arrays
  while (i < arr1.length && j < arr2.length) {
    if (arr2[j] > arr1[i]) {
      results.push(arr1[i]); // Push the smaller one to results
      i++; // Move pointer
    } else {
      results.push(arr2[j]);
      j++;
    }
  }

  // Handle remaining elements (Since they are already sorted, just push them all)
  while (i < arr1.length) {
    results.push(arr1[i]);
    i++;
  }
  while (j < arr2.length) {
    results.push(arr2[j]);
    j++;
  }

  return results;
}

// Test: merge([1, 10, 50], [2, 14, 99, 100])

3. Completing with Recursion

Now, we create the main sorting logic, mergeSort, using the merge function.

We use recursion to keep splitting the array in half and then come back up while merging them.

function mergeSort(arr) {
  // 1. Base Case: If length is 1 or less, it's already sorted
  if (arr.length <= 1) return arr;

  // 2. Split in half
  let mid = Math.floor(arr.length / 2);
  let left = mergeSort(arr.slice(0, mid)); // Recursive call
  let right = mergeSort(arr.slice(mid));   // Recursive call

  // 3. Merge the sorted left and right, then return
  return merge(left, right);
}

mergeSort([10, 24, 76, 73, 72, 1, 9]);

4. Performance Analysis: Why is it Fast?

Key Takeaways

"It's fast, but it eats up too much memory?"

Chris got greedy. Is there a dream algorithm that is fast with O(N log N) speed but doesn't use extra memory (O(1))?

Of course, there is. But that guy is a bit 'unstable' and prickly.

Let's go meet the King of sorting algorithms used most in the world, Quick Sort.

🔗 References