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

Concept Flow - Merge Sort as Divide and Conquer

Start: Full Array

↓

Divide Array into Two Halves

↓

Recursively Sort Left Half

→Recursively Sort Right Half

↓

Base Case: Single Element or Empty

↓

Merge Two Sorted Halves

↓

Return Merged Sorted Array

↓

Done

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

Execution Sample

DSA Java

int[] arr = {4, 3, 2, 1};
mergeSort(arr, 0, 3);
// Sorts arr in place

Sorts the array [4,3,2,1] using merge sort by dividing and merging.

Execution Table

Step	Operation	Subarray Indices	Action Detail	Array State
1	Divide	[0..3]	Split into [0..1] and [2..3]	[4, 3, 2, 1]
2	Divide	[0..1]	Split into [0..0] and [1..1]	[4, 3, 2, 1]
3	Base Case	[0..0]	Single element, no action	[4, 3, 2, 1]
4	Base Case	[1..1]	Single element, no action	[4, 3, 2, 1]
5	Merge	[0..1]	Merge [4] and [3] into sorted [3,4]	[3, 4, 2, 1]
6	Divide	[2..3]	Split into [2..2] and [3..3]	[3, 4, 2, 1]
7	Base Case	[2..2]	Single element, no action	[3, 4, 2, 1]
8	Base Case	[3..3]	Single element, no action	[3, 4, 2, 1]
9	Merge	[2..3]	Merge [2] and [1] into sorted [1,2]	[3, 4, 1, 2]
10	Merge	[0..3]	Merge [3,4] and [1,2] into sorted [1,2,3,4]	[1, 2, 3, 4]
11	Done	Full array	Sorted array complete	[1, 2, 3, 4]

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

Variable Tracker

Variable	Start	After Step 5	After Step 9	After Step 10	Final
arr	[4, 3, 2, 1]	[3, 4, 2, 1]	[3, 4, 1, 2]	[1, 2, 3, 4]	[1, 2, 3, 4]
left indices	[0..3]	[0..1]	[0..1]	[0..1]	[0..3]
right indices	[0..3]	[2..3]	[2..3]	[2..3]	[0..3]

Key Moments - 3 Insights

Why do we stop dividing when the subarray has one element?

Because a single element is already sorted, so no further division or sorting is needed (see steps 3 and 4 in execution_table).

How does merging two sorted halves keep the array sorted?

Merging compares elements from both halves and places the smaller one first, ensuring the combined array is sorted (see steps 5, 9, and 10).

Why do we merge after both halves are sorted?

Because merging relies on both halves being sorted to efficiently combine them into a sorted whole (see step 10 where two sorted halves merge).

Visual Quiz - 3 Questions

Look at the execution_table, what is the array state after step 5?

A [1, 2, 3, 4]

B [3, 4, 2, 1]

C [4, 3, 2, 1]

D [3, 4, 1, 2]

💡 Hint

Check the 'Array State' column at step 5 in execution_table.

At which step does the condition of single element subarray first occur?

A Step 3

B Step 1

C Step 5

D Step 9

💡 Hint

Look for 'Base Case' operations in execution_table.

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 occur but no swaps needed

D Division steps would be skipped

💡 Hint

Merging always happens after division regardless of initial order, see steps 5, 9, 10.

Concept Snapshot

Merge Sort divides array into halves recursively until single elements remain.
Then merges sorted halves step-by-step to form a sorted array.
Uses divide and conquer: divide, conquer (sort), merge.
Stable and efficient with O(n log n) time complexity.
Works by comparing elements during merge to keep order.

Full Transcript

Merge Sort works by dividing the array into two halves repeatedly until each subarray has only one element, which is naturally sorted. Then it merges these small sorted arrays back together by comparing elements and placing them in order. This process continues until the entire array is merged and sorted. The execution table shows each step: dividing, base cases, and merging with the array state after each operation. Key points include stopping division at single elements, merging sorted halves to keep order, and always merging after sorting both halves. The variable tracker shows how the array changes after merges. This method is efficient and stable, making it a popular sorting algorithm.

Practice

1. What is the main idea behind the Merge Sort algorithm in the context of divide and conquer?

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. Build a heap and extract elements in sorted order

Solution

1. Step 1: Understand divide and conquer in Merge Sort

   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 C

4. Quick Check:

   Divide and conquer = split, sort, merge [OK]

Hint: Remember: split, sort halves, then merge [OK]

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking Merge Sort uses pivot like Quick Sort
• Ignoring the merge step after dividing

2. Which of the following is the correct way to declare the merge function header in Java for merging two sorted subarrays in Merge Sort?

easy

A. int merge(int arr[], int start, int end)

B. void merge(int[] arr, int left, int mid, int right)

C. void merge(int arr[], int low, int high)

D. int merge(int[] arr, int left, int right)

Solution

1. Step 1: Identify parameters needed for merging

   The merge function needs the array and indices: left, mid, right to merge two halves.

2. Step 2: Check method signature correctness

   It returns void and takes int[] arr, int left, int mid, int right as parameters.

3. Final Answer:

   void merge(int[] arr, int left, int mid, int right) -> Option B

4. Quick Check:

   Correct merge signature = void merge(arr, left, mid, right) [OK]

Hint: Merge needs array and three indices: left, mid, right [OK]

Common Mistakes:

• Using wrong parameter names or missing mid index
• Returning int instead of void
• Confusing start/end with left/right without mid

3. What will be the output of the following Java code snippet using Merge Sort on the array [4, 1, 3, 9, 7]?

int[] arr = {4, 1, 3, 9, 7};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));

medium

A. [1, 4, 3, 7, 9]

B. [4, 1, 3, 7, 9]

C. [9, 7, 4, 3, 1]

D. [1, 3, 4, 7, 9]

Solution

1. Step 1: Apply Merge Sort to the array

   Merge Sort divides and merges to sort: [4,1,3,9,7] -> [1,3,4,7,9]

2. Step 2: Verify final sorted array

   The sorted array is ascending: [1, 3, 4, 7, 9]

3. Final Answer:

   [1, 3, 4, 7, 9] -> Option D

4. Quick Check:

   Sorted array = ascending order [OK]

Hint: Merge Sort always outputs sorted ascending array [OK]

Common Mistakes:

• Confusing merge step output with partial arrays
• Assuming original order remains
• Mixing up ascending and descending order

4. Identify the error in this Merge Sort merge function snippet:

void merge(int[] arr, int left, int mid, int right) {
  int n1 = mid - left;
  int n2 = right - mid;
  int[] L = new int[n1];
  int[] R = new int[n2];
  for (int i = 0; i < n1; i++) L[i] = arr[left + i];
  for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];
  // merging logic follows...
}

medium

A. Incorrect calculation of n1 size

B. Wrong copying of elements into R array

C. Missing return statement in void method

D. Using < instead of <= in for loops

Solution

1. Step 1: Check size calculations for subarrays

   n1 should be mid - left + 1 and n2 should be right - mid to cover all elements.

2. Step 2: Identify impact of wrong sizes

   Incorrect sizes cause array index errors or missing elements during merge.

3. Final Answer:

   Incorrect calculation of n1 size -> Option A

4. Quick Check:

   Sizes must include mid element [OK]

Hint: Remember: n1 = mid-left+1, n2 = right-mid [OK]

Common Mistakes:

• Forgetting +1 in n1 size calculation
• Copying elements starting at wrong index
• Confusing loop bounds with <= instead of <

5. Given an array with many duplicate values, how should the merge step in Merge Sort be adapted to maintain stability (preserve original order of equal elements)?

hard

A. When elements are equal, copy from the left subarray first

B. When elements are equal, copy from the right subarray first

C. Skip duplicates during merge to reduce array size

D. Sort duplicates separately after merge

Solution

1. Step 1: Understand stability in sorting

   Stable sort keeps equal elements in original order.

2. Step 2: Apply stability rule in merge step

   When equal, copy element from left subarray first to preserve order.

3. Final Answer:

   When elements are equal, copy from the left subarray first -> Option A

4. Quick Check:

   Left first on equals = stable merge [OK]

Hint: Copy left element first on equal values to keep stability [OK]

Common Mistakes:

• Copying right element first breaks stability
• Removing duplicates during merge
• Sorting duplicates separately after merge