Merge Sort as Divide and Conquer in DSA Javascript - Time & Space Complexity

Time Complexity: Merge Sort as Divide and Conquer

O(n log n)

Understanding Time Complexity

We want to understand how the time taken by merge sort changes as the list size grows.

How does splitting and merging affect the total work done?

Scenario Under Consideration

Analyze the time complexity of the following merge sort code.

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

This code splits the array into halves, sorts each half recursively, then merges the sorted halves.

Identify Repeating Operations

• Primary operation: Recursively splitting the array and merging sorted halves.
• How many times: The array is split about log₂(n) times, and merging happens at each level over all elements.

How Execution Grows With Input

Each split divides the array in half, creating about log₂(n) levels of splitting.

At each level, merging all parts touches all n elements once.

Input Size (n)	Approx. Operations
10	About 10 * 4 = 40
100	About 100 * 7 = 700
1000	About 1000 * 10 = 10,000

Pattern observation: Operations grow roughly as n times log n, which grows faster than n but much slower than n squared.

Final Time Complexity

Time Complexity: O(n log n)

This means the time grows a bit faster than the size of the input but much better than simple sorting methods that check every pair.

Common Mistake

[X] Wrong: "Merge sort is just a simple loop over the array, so it must be O(n)."

[OK] Correct: Merge sort splits the array many times and merges at each level, so it does more work than a single pass.

Interview Connect

Understanding merge sort's time complexity shows you how divide and conquer helps solve problems efficiently, a key skill in many coding challenges.

Self-Check

"What if we changed merge sort to split the array into three parts instead of two? How would the time complexity change?"

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