Merge Sort Algorithm in DSA Java - Execution Trace

Concept Flow - Merge Sort Algorithm

Start: Full array

↓

Divide array into halves

↓

Recursively sort left half

→Recursively sort right half

↓

Merge two sorted halves into one sorted array

↓

Return merged sorted array

↓

Done

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

Execution Sample

DSA Java

int[] arr = {5, 3, 8, 4};
mergeSort(arr, 0, arr.length - 1);
// Sorts the array using merge sort

This code sorts the array [5, 3, 8, 4] using merge sort by dividing and merging.

Execution Table

Step	Operation	Sub-array	Action	Array State
1	Divide	[5, 3, 8, 4]	Split into [5,3] and [8,4]	[5, 3, 8, 4]
2	Divide	[5, 3]	Split into [5] and [3]	[5, 3, 8, 4]
3	Base case	[5]	Single element, no action	[5, 3, 8, 4]
4	Base case	[3]	Single element, no action	[5, 3, 8, 4]
5	Merge	[5] and [3]	Compare 5 and 3, merge to [3,5]	[3, 5, 8, 4]
6	Divide	[8, 4]	Split into [8] and [4]	[3, 5, 8, 4]
7	Base case	[8]	Single element, no action	[3, 5, 8, 4]
8	Base case	[4]	Single element, no action	[3, 5, 8, 4]
9	Merge	[8] and [4]	Compare 8 and 4, merge to [4,8]	[3, 5, 4, 8]
10	Merge	[3,5] and [4,8]	Compare and merge to [3,4,5,8]	[3, 4, 5, 8]
11	Done	[3,4,5,8]	Array fully sorted	[3, 4, 5, 8]

💡 All sub-arrays reduced to single elements and merged back fully sorted.

Variable Tracker

Variable	Start	After Step 2	After Step 5	After Step 9	Final
arr	[5, 3, 8, 4]	[5, 3, 8, 4]	[3, 5, 8, 4]	[3, 5, 4, 8]	[3, 4, 5, 8]
left sub-array	N/A	[5, 3]	[3, 5]	[3, 5]	[3, 4, 5, 8]
right sub-array	N/A	[8, 4]	[8, 4]	[4, 8]	[3, 4, 5, 8]

Key Moments - 3 Insights

Why do we split the array until single elements?

Because single elements are already sorted, as shown in steps 3, 4, 7, and 8 in the execution_table.

How does merging keep the array sorted?

Merging compares elements from two sorted halves and picks the smaller one each time, as seen in steps 5, 9, and 10.

Why does the array state change after merging steps?

Because merging replaces the sub-array with a sorted version, updating the array state as shown in steps 5, 9, and 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 5, what is the array state after merging [5] and [3]?

A [3, 8, 5, 4]

B [3, 5, 8, 4]

C [5, 3, 8, 4]

D [5, 8, 3, 4]

💡 Hint

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

At which step does the right half [8,4] get merged into a sorted sub-array?

A Step 9

B Step 7

C Step 8

D Step 10

💡 Hint

Look for the 'Merge' operation involving [8] and [4] in the execution_table.

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

A Array state would become unsorted

B Array state would become reversed

C Array state would remain the same after merges

D Array state would shrink

💡 Hint

Consider how merging two sorted halves works as shown in the variable_tracker and execution_table.

Concept Snapshot

Merge Sort Algorithm:
- Divide array into halves recursively
- Base case: single element arrays
- Merge sorted halves by comparing elements
- Result is a fully sorted array
- Time complexity: O(n log n)
- Space complexity: O(n) due to merging

Full Transcript

Merge Sort works by splitting the array into smaller parts until each part has one element. Then it merges these parts back together in sorted order. The process repeats recursively for left and right halves. Each merge compares elements from two sorted halves and builds a bigger sorted array. This continues until the whole array is sorted. The execution table shows each step of dividing and merging, with the array state updating after merges. Key moments include understanding why single elements are base cases and how merging keeps order. The visual quiz tests understanding of array states at different 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. Divide the array into halves, sort each half, then merge them

B. Compare each element with every other element and swap if needed

C. Pick the smallest element and place it at the beginning repeatedly

D. Build a heap and extract elements in sorted order

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 to produce a fully sorted array.

3. Final Answer:

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

4. Quick Check:

   Merge Sort = Divide and Conquer [OK]

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

Common Mistakes:

• Confusing Merge Sort with Bubble Sort
• Thinking it sorts in place without merging
• Believing it picks smallest elements one by one

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

easy

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

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

C. void merge(int arr[], int start, int end)

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

Solution

1. Step 1: Identify parameters needed for merging

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

2. Step 2: Check return type and parameter order

   It returns nothing (void) and parameters match the signature in void merge(int[] arr, int left, int mid, int right).

3. Final Answer:

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

4. Quick Check:

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

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

Common Mistakes:

• Using wrong parameter order
• Returning int instead of void
• Missing mid index parameter

3. What will be the output of the following Java code snippet using Merge Sort on array {4, 1, 3, 2}?

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

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: Understand mergeSort on {4,1,3,2}

   It splits into {4,1} and {3,2}, sorts each half to {1,4} and {2,3}.

2. Step 2: Merge sorted halves

   Merging {1,4} and {2,3} results in fully sorted array {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 Sort always returns sorted array ascending [OK]

Common Mistakes:

• Confusing merge order
• Not sorting halves before merging
• Printing original unsorted array

4. Identify the bug in this merge function snippet for Merge Sort in Java:

void merge(int[] arr, int left, int mid, int right) {
  int n1 = mid - left + 1;
  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 + j];
  // merging logic follows...
}

medium

A. Array L should be of size n1 + 1

B. Lengths n1 and n2 should be mid - left + 1 and right - mid

C. Copying elements from arr to R should start from mid + 1

D. No bug, code is correct

Solution

1. Step 1: Check array lengths and copying ranges

   Lengths n1 = mid - left + 1 and n2 = right - mid are correct for the left half (left to mid) and right half (mid+1 to right).

2. Step 2: Verify copying elements to R array

   Copying to R starts at arr[mid], but it should start at arr[mid + 1] to avoid overlap.

3. Final Answer:

   Copying elements from arr to R should start from mid + 1 -> Option C

4. Quick Check:

   Right half copy starts at mid+1 [OK]

Hint: Right half starts copying from mid+1, not mid [OK]

Common Mistakes:

• Starting right half copy at mid instead of mid+1
• Incorrect array length calculation
• Assuming no overlap in copying

5. Given an array with many duplicate elements, how can you modify Merge Sort to maintain the original order of equal elements (stable sort)?

hard

A. When merging, always pick from the right subarray first

B. Merge Sort cannot be stable with duplicates

C. Use a hash map to track duplicates and reorder after sorting

D. When merging, if elements are equal, pick from the left subarray first

Solution

1. Step 1: Understand stability in sorting

   A stable sort keeps equal elements in their original order.

2. Step 2: Modify merge step for stability

   When merging, if elements are equal, always choose the element from the left subarray first to preserve order.

3. Final Answer:

   When merging, if elements are equal, pick from the left subarray first -> Option D

4. Quick Check:

   Stable merge picks left element first on ties [OK]

Hint: Pick left element first when equal to keep order [OK]

Common Mistakes:

• Picking right element first breaks stability
• Thinking Merge Sort is unstable by default
• Using extra data structures unnecessarily