Merge Sort as Divide and Conquer in DSA Python - 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 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 order.

Execution Sample

DSA Python

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr)//2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# Example
arr = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(arr))  # [3, 9, 10, 27, 38, 43, 82]

Full implementation: recursive divide via merge_sort, conquer via merge helper that combines two sorted lists efficiently.

Execution Table

Step	Operation	Array Segment	Action Detail	Resulting Array Segment
1	Start	[38, 27, 43, 3, 9, 82, 10]	Full array to sort	[38, 27, 43, 3, 9, 82, 10]
2	Divide	[38, 27, 43, 3, 9, 82, 10]	Split into left [38, 27, 43] and right [3, 9, 82, 10]
3	Divide Left	[38, 27, 43]	Split into [38] and [27, 43]
4	Divide Left-Right	[27, 43]	Split into [27] and [43]
5	Merge	[27] and [43]	Merge sorted [27] and [43]	[27, 43]
6	Merge	[38] and [27, 43]	Merge sorted [38] and [27, 43]	[27, 38, 43]
7	Divide Right	[3, 9, 82, 10]	Split into [3, 9] and [82, 10]
8	Divide Right-Left	[3, 9]	Split into [3] and [9]
9	Merge	[3] and [9]	Merge sorted [3] and [9]	[3, 9]
10	Divide Right-Right	[82, 10]	Split into [82] and [10]
11	Merge	[82] and [10]	Merge sorted [82] and [10]	[10, 82]
12	Merge	[3, 9] and [10, 82]	Merge sorted [3, 9] and [10, 82]	[3, 9, 10, 82]
13	Merge	[27, 38, 43] and [3, 9, 10, 82]	Merge sorted left and right halves	[3, 9, 10, 27, 38, 43, 82]
14	End	[3, 9, 10, 27, 38, 43, 82]	Fully sorted array	[3, 9, 10, 27, 38, 43, 82]

💡 All subarrays reduced to single elements and merged back sorted, completing the sort.

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] and [3, 9, 82, 10]	[27, 38, 43] and [3, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
left	N/A	[38, 27, 43]	[27, 38, 43]	[27, 38, 43]	N/A
right	N/A	[3, 9, 82, 10]	[3, 9, 82, 10]	[3, 9, 10, 82]	N/A

Key Moments - 3 Insights

Why do we stop dividing when the array segment has only one element?

Because a single element is already sorted, so no further division is needed. See Step 4 and Step 10 where arrays like [27] or [82] are returned as is.

How does the merge step combine two sorted arrays into one sorted array?

It compares the smallest elements of both arrays and picks the smaller one step-by-step until all elements are merged. Refer to Steps 5, 6, 9, 11, 12, and 13 for merging actions.

Why do we need to merge after sorting left and right halves?

Because sorting halves separately doesn't sort the whole array. Merging combines these sorted halves into a fully sorted array. See Step 13 where final merge happens.

Visual Quiz - 3 Questions

Look at the execution table, what is the array segment after Step 6?

A [38, 27, 43]

B [3, 9, 10, 82]

C [27, 38, 43]

D [27, 43]

💡 Hint

Check the 'Resulting Array Segment' column at Step 6 in the execution table.

At which step does the merge of the right half's two smallest arrays happen?

A Step 12

B Step 9

C Step 11

D Step 13

💡 Hint

Look for merging of [3] and [9] in the execution table.

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

A Merge steps would still happen but no swaps needed

B Merge steps would be skipped

C Array would be divided fewer times

D Merge steps would reverse the array

💡 Hint

Merge always happens to combine halves; sorting means no swaps during merge.

Concept Snapshot

Merge Sort splits array into halves recursively.
Each half is sorted separately.
Sorted halves are merged step-by-step.
Base case: single element arrays.
Result: fully sorted array after all merges.

Full Transcript

Merge Sort works by dividing the array into two halves repeatedly until each subarray has one element. Then it merges these small sorted arrays back together in order. The process uses recursion to handle the division and merging. The base case is when the array segment has one or zero elements, which are already sorted. Merging compares elements from two sorted arrays and builds a combined sorted array. This continues until the entire array is sorted. The execution table shows each step of dividing and merging with the array segments involved. The variable tracker follows how the array and its parts change after key steps. Key moments clarify why division stops at one element, how merging works, and why merging is necessary. The visual quiz tests understanding of array states at different steps and the behavior if the array is already sorted.

Practice

1. What is the main idea behind the Merge Sort algorithm?

easy

A. Insert elements one by one into a sorted list

B. Sort the list by repeatedly swapping adjacent elements

C. Select a pivot and partition the list around it

D. Divide the list into halves, sort each half, then merge them

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into smaller parts to simplify sorting.

2. Step 2: Merge sorted halves

   After sorting each half, it merges them to form a sorted list.

3. Final Answer:

   Divide the list into halves, sort each half, then merge them -> Option D

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 merge sort sorts in place without merging
• Mixing merge sort with quicksort pivot method

2. Which of the following is the correct base case condition in a recursive merge sort function in Python?

easy

A. if len(arr) > 1: return arr

B. if len(arr) <= 1: return arr

C. if arr is None: return []

D. if len(arr) == 0: return None

Solution

1. Step 1: Identify when recursion should stop

   Merge sort stops splitting when the list has 1 or 0 elements.

2. Step 2: Correct base case condition

   Checking if length is less than or equal to 1 returns the list as is.

3. Final Answer:

   if len(arr) <= 1: return arr -> Option B

4. Quick Check:

   Base case = list size ≤ 1 [OK]

Hint: Base case: list with 0 or 1 element is already sorted [OK]

Common Mistakes:

• Using wrong base case like len(arr) == 0 only
• Returning None instead of the list
• Incorrect condition that never stops recursion

3. What is the output of the following code?

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([4, 1, 3, 2]))

medium

A. [1, 2, 3, 4]

B. [4, 3, 2, 1]

C. [1, 3, 2, 4]

D. [2, 1, 4, 3]

Solution

1. Step 1: Trace recursive splitting

   List splits into [4,1] and [3,2], then further splits until single elements.

2. Step 2: Merge sorted halves

   Merge combines sorted lists step-by-step to form [1,2,3,4].

3. Final Answer:

   [1, 2, 3, 4] -> Option A

4. Quick Check:

   Sorted list = [1, 2, 3, 4] [OK]

Hint: Merge sort always returns sorted list ascending [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Forgetting to extend remaining elements after loop
• Mixing up indices i and j in merge

4. Find the error in this merge sort implementation:

def merge_sort(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

medium

A. Base case should be len(arr) <= 1, not len(arr) == 1

B. Merge function should use <= instead of < in comparison

C. Indices i and j should start at 1, not 0

D. Should return arr before checking base case

Solution

1. Step 1: Check base case condition

   Base case only handles lists of length 1, but empty lists cause infinite recursion.

2. Step 2: Correct base case to include empty list

   Change condition to len(arr) <= 1 to handle empty and single element lists.

3. Final Answer:

   Base case should be len(arr) <= 1, not len(arr) == 1 -> Option A

4. Quick Check:

   Base case must handle empty or single element [OK]

Hint: Base case must cover empty and single element lists [OK]

Common Mistakes:

• Using strict equality for base case
• Starting indices at 1 causing index errors
• Changing comparison operator unnecessarily

5. Given a list of 8 elements, how many times will the merge function be called during a full merge sort?

hard

A. 8

B. 15

C. 7

D. 16

Solution

1. Step 1: Understand merge calls in merge sort

   Merge is called once for each internal node in the recursion tree (combining two sorted sublists).

2. Step 2: Calculate number of merge calls for 8 elements

   4 merges (size 2 sublists) + 2 merges (size 4) + 1 merge (size 8) = 7 total. Formula: n - 1 = 7.

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Merge calls = n - 1 = 7 [OK]

Hint: Total merges in merge sort = n - 1 [OK]

Common Mistakes:

• Counting only top-level merges
• Confusing merges with splits
• Using 2n-1 (confusing with total recursive calls to merge_sort)