Why Merge Sort as Divide and Conquer in DSA Javascript?

The Big Idea

Discover how breaking a big problem into small parts makes sorting fast and easy!

The Scenario

Imagine you have a messy pile of playing cards scattered on a table. You want to sort them by number, but you try to pick one card at a time and find its correct place by comparing it to every other card manually.

The Problem

This manual way is slow and confusing because you keep checking many cards again and again. It's easy to lose track or make mistakes, especially if the pile is very big.

The Solution

Merge Sort breaks the big pile into smaller piles, sorts each small pile easily, and then carefully merges them back together in order. This way, you only compare small groups at a time, making sorting faster and less error-prone.

Before vs After

✗ Before

function manualSort(array) {
  for (let i = 0; i < array.length; i++) {
    for (let j = i + 1; j < array.length; j++) {
      if (array[i] > array[j]) {
        let temp = array[i];
        array[i] = array[j];
        array[j] = temp;
      }
    }
  }
  return array;
}

✓ After

function mergeSort(array) {
  if (array.length <= 1) return array;
  const middle = Math.floor(array.length / 2);
  const left = mergeSort(array.slice(0, middle));
  const right = mergeSort(array.slice(middle));
  return merge(left, right);
}
function merge(left, right) {
  const 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);
}

What It Enables

It enables sorting large amounts of data quickly and reliably by breaking problems into smaller, manageable pieces.

Real Life Example

When you organize thousands of contacts on your phone, merge sort helps your phone quickly sort them by name or number without freezing or errors.

Key Takeaways

Manual sorting is slow and error-prone for big data.

Merge Sort uses divide and conquer to simplify sorting.

It merges small sorted parts to build a fully sorted list efficiently.

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