Merge Sort as Divide and Conquer in DSA Javascript - Execution Trace

Concept Flow - Merge Sort as Divide and Conquer

Start with full array

↓

Divide array into two halves

↓

Recursively sort left half

→Recursively sort right half

↓

Merge two sorted halves

↓

Sorted array

Merge Sort splits the array into halves recursively, sorts each half, then merges them back in order.

Execution Sample

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

This code splits the array, sorts each half recursively, then merges them.

Execution Table

Step	Operation	Array State	Subarrays Divided	Merge Action	Resulting Array
1	Start	[38, 27, 43, 3, 9, 82, 10]	Full array	None	[38, 27, 43, 3, 9, 82, 10]
2	Divide	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43] and [3, 9, 82, 10]	None	N/A
3	Divide Left Half	[38, 27, 43]	[38] and [27, 43]	None	N/A
4	Divide Right Half of Left	[27, 43]	[27] and [43]	None	N/A
5	Merge	Left: [27], Right: [43]	N/A	Compare 27 and 43	[27, 43]
6	Merge	Left: [38], Right: [27, 43]	N/A	Compare 38 and 27, then 38 and 43	[27, 38, 43]
7	Divide Right Half	[3, 9, 82, 10]	[3, 9] and [82, 10]	None	N/A
8	Divide Left Half of Right	[3, 9]	[3] and [9]	None	N/A
9	Merge	Left: [3], Right: [9]	N/A	Compare 3 and 9	[3, 9]
10	Divide Right Half of Right	[82, 10]	[82] and [10]	None	N/A
11	Merge	Left: [82], Right: [10]	N/A	Compare 82 and 10	[10, 82]
12	Merge	Left: [3, 9], Right: [10, 82]	N/A	Compare 3 and 10, 9 and 10	[3, 9, 10, 82]
13	Merge	Left: [27, 38, 43], Right: [3, 9, 10, 82]	N/A	Compare elements stepwise	[3, 9, 10, 27, 38, 43, 82]
14	End	[3, 9, 10, 27, 38, 43, 82]	Sorted full array	None	[3, 9, 10, 27, 38, 43, 82]

💡 All subarrays reduced to single elements and merged back sorted.

Variable Tracker

Variable	Start	After Step 2	After Step 6	After Step 12	Final
arr	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43] and [3, 9, 82, 10]	[27, 38, 43]	[3, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
left	N/A	[38, 27, 43]	[27, 43]	[3, 9]	[27, 38, 43]
right	N/A	[3, 9, 82, 10]	[43]	[10, 82]	[3, 9, 10, 82]
merged	N/A	N/A	[27, 43]	[3, 9]	[3, 9, 10, 27, 38, 43, 82]

Key Moments - 3 Insights

Why do we keep dividing the array until subarrays have only one element?

Because a single element array is already sorted, so merging them back is easier and guarantees sorted order (see steps 3,4,8,10).

How does the merge step keep the array sorted?

Merge compares the smallest elements of two sorted subarrays and picks the smaller one step-by-step, building a sorted merged array (see steps 5,6,9,11,12,13).

Why do we need to merge after dividing?

Dividing breaks the problem into smaller sorted parts; merging combines these sorted parts into a fully sorted array (see step 13 merging left and right halves).

Visual Quiz - 3 Questions

Look at the execution table at step 6, what is the resulting array after merging?

A [27, 38, 43]

B [38, 27, 43]

C [27, 43, 38]

D [43, 27, 38]

💡 Hint

Check the 'Resulting Array' column at step 6 in the execution_table.

At which step does the merge of the right half subarrays [3,9] and [10,82] happen?

A Step 9

B Step 12

C Step 11

D Step 13

💡 Hint

Look for merging action involving [3,9] and [10,82] in the 'Merge Action' column.

If the initial array was already sorted, how would the merge steps change?

A Array would be reversed

B Merge steps would be skipped

C Merge steps would still compare and merge but no swaps needed

D Divide steps would be skipped

💡 Hint

Merge always compares elements even if array is sorted; see merge actions in execution_table.

Concept Snapshot

Merge Sort splits array into halves recursively.
Sorts each half separately.
Merges sorted halves step-by-step.
Runs in O(n log n) time.
Stable and uses extra space for merging.

Full Transcript

Merge Sort works by dividing the array into smaller parts until each part has one element. Then it merges these parts back together in sorted order. The process is recursive: split, sort left half, sort right half, then merge. The merge step compares elements from two sorted subarrays and builds a new sorted array. This continues until the full array is sorted. The execution table shows each divide and merge step with array states. Variables track the current subarrays and merged results. Key moments clarify why dividing to single elements is needed and how merging keeps order. The quiz tests understanding of merge results and steps. Merge Sort is efficient and stable, making it a popular sorting method.

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