Merge Sort Algorithm 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 that uses merge sort on the array [4, 1, 3, 2]?

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

console.log(mergeSort([4, 1, 3, 2]));

A [1, 2, 3, 4]

B [4, 3, 2, 1]

C [1, 3, 2, 4]

D [2, 1, 3, 4]

💡 Hint

Think about how merge sort splits and merges arrays in sorted order.

Merge sort splits the array into halves recursively and merges them back in sorted order. The final output is the sorted array [1, 2, 3, 4].

🧠 Conceptual

intermediate

Time Complexity of Merge Sort

What is the time complexity of the merge sort algorithm in the average and worst cases?

A O(n)

B O(n^2)

C O(log n)

D O(n log n)

💡 Hint

Consider how many times the array is split and merged.

Merge sort divides the array into halves log n times and merges n elements each time, resulting in O(n log n) time complexity.

🔧 Debug

advanced

Identify the error in this merge function

What error will occur when running this merge function used in 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));
}

A SyntaxError: Unexpected token

B TypeError: Cannot read property of undefined

C No error, returns sorted array

D Infinite loop

💡 Hint

Check the loop condition and array indexing carefully.

The loop condition uses <= which allows i or j to equal the array length, causing undefined access and TypeError.

🚀 Application

advanced

Using Merge Sort to Sort Objects by a Key

Given an array of objects [{name: 'Bob', age: 25}, {name: 'Alice', age: 30}, {name: 'Eve', age: 22}], which option correctly sorts the array by age 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].age < right[j].age) {
      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 people = [{name: 'Bob', age: 25}, {name: 'Alice', age: 30}, {name: 'Eve', age: 22}];
console.log(mergeSort(people));

A [{"name":"Eve","age":22},{"name":"Alice","age":30},{"name":"Bob","age":25}]

B [{"name":"Bob","age":25},{"name":"Eve","age":22},{"name":"Alice","age":30}]

C [{"name":"Eve","age":22},{"name":"Bob","age":25},{"name":"Alice","age":30}]

D [{"name":"Alice","age":30},{"name":"Bob","age":25},{"name":"Eve","age":22}]

💡 Hint

Check the comparison inside the merge function uses the age property.

The merge function compares objects by their age property, so the sorted array is by ascending age: Eve (22), Bob (25), Alice (30).

🧠 Conceptual

expert

Space Complexity of Merge Sort

What is the space complexity of the merge sort algorithm and why?

A O(n) because merge sort requires extra space to hold merged arrays

B O(1) because merge sort sorts in place without extra space

C O(log n) because only recursive call stack uses space

D O(n log n) because it creates new arrays at each recursion level

💡 Hint

Think about the temporary arrays created during merging.

Merge sort uses extra space proportional to the input size to store merged arrays, so space complexity is O(n).

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Insert elements one by one into a sorted sublist

B. Sort the array by repeatedly swapping adjacent elements

C. Pick a pivot and partition the array around it

D. Divide the array into halves, sort each half, then merge them

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

   It then merges these sorted halves back together to form a sorted array.

3. Final Answer:

   Divide the array into halves, sort each half, then merge them -> Option D

4. Quick Check:

   Merge Sort = Divide, sort halves, merge [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 extra space

2. Which of the following is the correct way to split an array arr into two halves in JavaScript for Merge Sort?

easy

A. const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid);

B. const mid = arr.length / 2; const left = arr.splice(0, mid); const right = arr.splice(mid);

C. const mid = arr.length / 2; const left = arr.slice(mid); const right = arr.slice(0, mid);

D. const mid = Math.ceil(arr.length / 2); const left = arr.slice(mid); const right = arr.slice(0, mid);

Solution

1. Step 1: Calculate middle index correctly

   Use Math.floor to get the middle index for even or odd lengths.

2. Step 2: Use slice to split without modifying original array

   Slice(0, mid) gets left half; slice(mid) gets right half correctly.

3. Final Answer:

   const mid = Math.floor(arr.length / 2); const left = arr.slice(0, mid); const right = arr.slice(mid); -> Option A

4. Quick Check:

   Use Math.floor and slice for splitting [OK]

Hint: Use Math.floor and slice to split arrays safely [OK]

Common Mistakes:

• Using splice which modifies the original array
• Not flooring the middle index causing float errors
• Swapping left and right halves incorrectly

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

console.log(mergeSort([4, 1, 3, 2]));

medium

A. [1, 3, 2, 4]

B. [4, 3, 2, 1]

C. [1, 2, 3, 4]

D. [2, 1, 3, 4]

Solution

1. Step 1: Recursively split and sort the array

   The array [4,1,3,2] is split into [4,1] and [3,2], then further until single elements.

2. Step 2: Merge sorted halves step-by-step

   Merge [4] and [1] to [1,4], merge [3] and [2] to [2,3], then merge [1,4] and [2,3] to [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option C

4. Quick Check:

   Sorted array = [1, 2, 3, 4] [OK]

Hint: Trace splits and merges carefully to find sorted output [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Not handling empty arrays in merge
• Using shift inefficiently causing performance issues

4. Identify the bug in this Merge Sort implementation:

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

medium

A. Base case should be arr.length <= 1, not arr.length === 1

B. Using shift() inside merge causes infinite loop

C. Math.floor should be Math.ceil for mid calculation

D. merge function should return result.reverse()

Solution

1. Step 1: Check base case condition

   Base case returns when array length is 1, but it should also handle empty arrays (length 0) to avoid errors.

2. Step 2: Correct base case to include empty arrays

   Change condition to arr.length <= 1 to safely return arrays of length 0 or 1.

3. Final Answer:

   Base case should be arr.length <= 1, not arr.length === 1 -> Option A

4. Quick Check:

   Base case = arr.length <= 1 [OK]

Hint: Base case must handle empty arrays too [OK]

Common Mistakes:

• Ignoring empty array base case causing stack overflow
• Incorrect mid calculation causing wrong splits
• Misunderstanding shift() usage as a bug

5. You want to sort a large array of objects by a numeric property score using Merge Sort. Which modification is needed in the merge function to correctly sort by score?

hard

A. Use JSON.stringify to compare objects

B. Compare left[0].score and right[0].score instead of elements directly

C. Convert objects to strings before comparing

D. Sort only keys, then map back to objects

Solution

1. Step 1: Understand sorting objects by property

   Objects cannot be compared directly; comparison must use the numeric property score.

2. Step 2: Modify merge comparison to use score

   Change condition to compare left[0].score and right[0].score to merge correctly.

3. Final Answer:

   Compare left[0].score and right[0].score instead of elements directly -> Option B

4. Quick Check:

   Compare object properties for sorting [OK]

Hint: Compare object properties, not whole objects [OK]

Common Mistakes:

• Trying to compare objects directly causing NaN or errors
• Using string conversion which breaks numeric order
• Sorting keys separately losing object structure