Merge Sort Algorithm in DSA Javascript - Execution Trace

Concept Flow - Merge Sort Algorithm

Start with full array

↓

Divide array into two halves

↓

Recursively apply merge sort on left half

↓

Base case: single element or empty array

↓

Merge two sorted halves

↓

Sorted array

↓

Done

Merge Sort splits the array into halves recursively until single elements remain, then merges these sorted parts back together.

Execution Sample

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++]);
    } else {
      result.push(right[j++]);
    }
  }
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
  return result;
}

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

// Example usage:
// mergeSort([38, 27, 43, 3, 9, 82, 10]) => [3, 9, 10, 27, 38, 43, 82]

This complete code defines the `merge` function to combine two sorted arrays and `mergeSort` which recursively divides the array and merges sorted halves to produce a fully sorted array.

Execution Table

Step	Operation	Array State	Action	Visual State
1	Start	[38, 27, 43, 3, 9, 82, 10]	Split into two halves	[38, 27, 43, 3] | [9, 82, 10]
2	Split left half	[38, 27, 43, 3]	Split into [38, 27] and [43, 3]	[38, 27] | [43, 3] | [9, 82, 10]
3	Split left-left	[38, 27]	Split into [38] and [27]	[38] | [27] | [43, 3] | [9, 82, 10]
4	Base case left-left-left	[38]	Single element, return as is	[38] | [27] | [43, 3] | [9, 82, 10]
5	Base case left-left-right	[27]	Single element, return as is	[38] | [27] | [43, 3] | [9, 82, 10]
6	Merge left-left	[38] and [27]	Compare and merge	[27, 38] | [43, 3] | [9, 82, 10]
7	Split left-right	[43, 3]	Split into [43] and [3]	[27, 38] | [43] | [3] | [9, 82, 10]
8	Base case left-right-left	[43]	Single element, return as is	[27, 38] | [43] | [3] | [9, 82, 10]
9	Base case left-right-right	[3]	Single element, return as is	[27, 38] | [43] | [3] | [9, 82, 10]
10	Merge left-right	[43] and [3]	Compare and merge	[27, 38] | [3, 43] | [9, 82, 10]
11	Merge left half	[27, 38] and [3, 43]	Compare and merge	[3, 27, 38, 43] | [9, 82, 10]
12	Split right half	[9, 82, 10]	Split into [9] and [82, 10]	[3, 27, 38, 43] | [9] | [82, 10]
13	Base case right-left	[9]	Single element, return as is	[3, 27, 38, 43] | [9] | [82, 10]
14	Split right-right	[82, 10]	Split into [82] and [10]	[3, 27, 38, 43] | [9] | [82] | [10]
15	Base case right-right-left	[82]	Single element, return as is	[3, 27, 38, 43] | [9] | [82] | [10]
16	Base case right-right-right	[10]	Single element, return as is	[3, 27, 38, 43] | [9] | [82] | [10]
17	Merge right-right	[82] and [10]	Compare and merge	[3, 27, 38, 43] | [9] | [10, 82]
18	Merge right half	[9] and [10, 82]	Compare and merge	[3, 27, 38, 43] | [9, 10, 82]
19	Merge full array	[3, 27, 38, 43] and [9, 10, 82]	Compare and merge	[3, 9, 10, 27, 38, 43, 82]
20	Done	[3, 9, 10, 27, 38, 43, 82]	Sorted array returned	[3, 9, 10, 27, 38, 43, 82]

💡 All subarrays reduced to single elements and merged back in sorted order

Variable Tracker

Variable	Start	After Step 1	After Step 6	After Step 11	After Step 18	Final
arr	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43, 3] and [9, 82, 10]	[27, 38]	[3, 27, 38, 43]	[9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
left	undefined	[38, 27, 43, 3]	[27, 38]	[3, 27, 38, 43]	[9]	[3, 9, 10, 27, 38, 43, 82]
right	undefined	[9, 82, 10]	[43, 3]	[9, 82, 10]	[10, 82]	[3, 9, 10, 27, 38, 43, 82]
mid	undefined	3	1	2	1	N/A

Key Moments - 3 Insights

Why do we split the array until single elements remain?

Because single elements are already sorted, so merging them step-by-step creates a sorted array. See execution_table rows 4,5,8,9,13,15,16 where base cases return single elements.

How does the merge step combine two sorted arrays?

It compares the first elements of both arrays and picks the smaller one, repeating until all elements are merged. See execution_table rows 6,10,11,17,18,19 for merging steps showing array states.

Why do we use recursion in merge sort?

Recursion helps break down the problem into smaller parts (divide), then combine results (conquer). The recursive calls split arrays until base cases, then merge back. See execution_table steps 2-19 for recursive splitting and merging.

Visual Quiz - 3 Questions

Look at the execution_table at step 6, what is the merged array state?

A [27, 38]

B [38, 27]

C [38]

D [27]

💡 Hint

Check the Visual State column at step 6 in execution_table

At which step does the right half first get split into two parts?

A Step 18

B Step 12

C Step 14

D Step 10

💡 Hint

Look for the first split operation on the right half in execution_table

If the initial array had only one element, what would happen?

A The array is split into two empty arrays

B The merge step is called twice

C The function returns immediately without splitting

D The array is sorted by swapping elements

💡 Hint

Refer to base case handling in execution_table steps 4,5,8,9

Concept Snapshot

Merge Sort Algorithm:
- Recursively split array into halves until single elements
- Merge sorted halves by comparing elements
- Time complexity: O(n log n)
- Stable and works well for large data
- Uses extra space for merging
- Divide and conquer approach

Full Transcript

Merge Sort Algorithm splits the array into two halves recursively until each subarray has one element. These single elements are considered sorted. Then, it merges these sorted subarrays step-by-step by comparing their elements to form larger sorted arrays. This process continues until the entire array is merged back into a sorted array. The key steps are splitting, base case handling, and merging. The algorithm uses recursion to divide the problem and conquer by merging. It is efficient with O(n log n) time complexity and stable sorting behavior.

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