Merge Sort as Divide and Conquer in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to split the array into two halves.

DSA Javascript

const mid = Math.floor(arr.length [1] 2);

Drag options to blanks, or click blank then click option'

A*

B/

C+

D-

Attempts:

3 left

💡 Hint

Common Mistakes

Using addition or subtraction instead of division.

Using multiplication which increases the number.

We divide the length of the array by 2 to find the middle index.

2fill in blank

medium

Complete the code to recursively sort the left half of the array.

DSA Javascript

const left = mergeSort(arr.slice(0, [1]));

Drag options to blanks, or click blank then click option'

Aarr

Barr.length

C0

Dmid

Attempts:

3 left

💡 Hint

Common Mistakes

Using the full array length instead of mid.

Using 0 as the end index which results in an empty array.

We slice the array from 0 to mid to get the left half.

3fill in blank

hard

Fix the error in the merge function to correctly merge two sorted arrays.

DSA Javascript

while (i < left.length && j [1] right.length) {

Drag options to blanks, or click blank then click option'

A==

B>

C<

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using greater than which causes the loop to never run.

Using equality which stops the loop too early.

We continue merging while both pointers are within their array lengths.

4fill in blank

hard

Fill both blanks to complete the merge function's comparison and push logic.

DSA Javascript

if (left[i] [1] right[j]) {
  result.push(left[[2]]);
  i++;
} else {

Drag options to blanks, or click blank then click option'

A<

B>

Ci

Dj

Attempts:

3 left

💡 Hint

Common Mistakes

Using > instead of < in comparison.

Pushing right[j] instead of left[i] in the if block.

We compare left[i] < right[j] and push left[i] if true.

5fill in blank

hard

Fill all three blanks to complete the merge function's return statement with remaining elements.

DSA Javascript

return result.concat(left.slice([1])).concat(right.slice([2]));

// i and j track positions in left and right arrays
// [3] and [4] are the variables to use

Drag options to blanks, or click blank then click option'

Ai

Bj

Cleft

Dright

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong variables for slicing remaining elements.

Not concatenating remaining elements causing missing data.

We slice left from i and right from j to add remaining elements after merging.

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