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).