Merge Sort as Divide and Conquer in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Merge Sort on a small array

What is the output of the following JavaScript code after sorting the array using merge sort?

DSA Javascript

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));
}

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);
}

const array = [5, 3, 8, 4];
console.log(mergeSort(array));

A [8, 5, 4, 3]

B [5, 3, 8, 4]

C [3, 4, 5, 8]

D [3, 5, 4, 8]

💡 Hint

Think about how merge sort splits the array and merges sorted halves.

Merge sort splits the array into halves recursively until single elements remain, then merges them back in sorted order. The final sorted array is [3, 4, 5, 8].

🧠 Conceptual

intermediate

Understanding the divide step in merge sort

In merge sort, what is the main purpose of the divide step?

A To split the array into smaller parts until each part has one element

B To merge two sorted arrays into one sorted array

C To swap elements to sort the array in place

D To find the largest element in the array

💡 Hint

Divide step breaks the problem into smaller pieces.

The divide step splits the array into smaller parts until each part has only one element, which is the base case for merge sort.

❓ Predict Output

advanced

Output of merge function with two sorted arrays

What is the output of the merge function when merging these two sorted arrays: [1, 4, 7] and [2, 3, 6]?

DSA Javascript

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(merge([1, 4, 7], [2, 3, 6]));

A [1, 2, 3, 4, 6, 7]

B [1, 4, 7, 2, 3, 6]

C [2, 3, 6, 1, 4, 7]

D [1, 2, 3, 6, 4, 7]

💡 Hint

The merge function combines two sorted arrays into one sorted array.

The merge function compares elements from both arrays and adds the smaller one to the result, producing a fully sorted merged array.

🔧 Debug

advanced

Identify the error in this merge sort implementation

What error will occur when running this merge sort code?

DSA Javascript

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([3, 1, 2]));

A TypeError because merge is undefined

B Returns the original unsorted array

C SyntaxError due to missing return statement

D Stack overflow due to infinite recursion

💡 Hint

Check the base case condition for recursion.

The base case uses 'arr.length < 1' which never stops recursion for arrays of length 1, causing infinite recursion and stack overflow.

🚀 Application

expert

Number of comparisons in merge sort for 8 elements

What is the maximum number of element comparisons performed by merge sort when sorting an array of 8 elements?

A 19

B 17

C 15

D 24

💡 Hint

Think about how many comparisons happen at each merge step and sum them.

Merge sort performs at most n*log2(n) comparisons. For n=8, log2(8)=3, so max comparisons ≈ 8*3=24 but exact max is 17 due to merge steps.

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