Merge Sort Algorithm in DSA Python - Execution Trace

Concept Flow - Merge Sort Algorithm

Start with full array

↓

Divide array into two halves

↓

Recursively apply merge sort on left half

→Recursively apply merge sort on right half

↓

Sorted left half

↓

Merge two sorted halves into one sorted array

↓

Sorted full array

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)

This code splits the array recursively and merges sorted halves.

Execution Table

Step	Operation	Array State	Subarrays Divided	Merge Action	Visual State
1	Start	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43] and [3, 9, 82, 10]	None	[38, 27, 43, 3, 9, 82, 10]
2	Divide Left Half	[38, 27, 43]	[38] and [27, 43]	None	[38] and [27, 43]
3	Divide Right Half of Left	[27, 43]	[27] and [43]	None	[27] and [43]
4	Merge [27] and [43]	N/A	N/A	Merge to [27, 43]	[38] and [27, 43]
5	Merge [38] and [27, 43]	N/A	N/A	Merge to [27, 38, 43]	[27, 38, 43]
6	Divide Right Half	[3, 9, 82, 10]	[3, 9] and [82, 10]	None	[3, 9] and [82, 10]
7	Divide Left Half of Right	[3, 9]	[3] and [9]	None	[3] and [9]
8	Merge [3] and [9]	N/A	N/A	Merge to [3, 9]	[3, 9]
9	Divide Right Half of Right	[82, 10]	[82] and [10]	None	[82] and [10]
10	Merge [82] and [10]	N/A	N/A	Merge to [10, 82]	[10, 82]
11	Merge [3, 9] and [10, 82]	N/A	N/A	Merge to [3, 9, 10, 82]	[3, 9, 10, 82]
12	Merge [27, 38, 43] and [3, 9, 10, 82]	N/A	N/A	Merge to [3, 9, 10, 27, 38, 43, 82]	[3, 9, 10, 27, 38, 43, 82]
13	End	[3, 9, 10, 27, 38, 43, 82]	N/A	N/A	[3, 9, 10, 27, 38, 43, 82]

💡 All subarrays reduced to size 1 and merged back in sorted order

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 5	After Step 8	After Step 10	After Step 11	Final
arr	[38, 27, 43, 3, 9, 82, 10]	[38, 27, 43]	[27, 38, 43]	[27, 38, 43]	[3, 9]	[10, 82]	[3, 9, 10, 82]	[3, 9, 10, 27, 38, 43, 82]
left	N/A	[38, 27, 43]	[27]	[27, 43]	[3, 9]	[82]	[3, 9, 10, 82]	N/A
right	N/A	[3, 9, 82, 10]	[38]	[38]	[9]	[10]	[27, 38, 43]	N/A

Key Moments - 3 Insights

Why do we stop dividing when the subarray size is 1?

Because a single element is already sorted, so no further division is needed. See execution_table rows 3 and 7 where arrays like [27] and [3] are not divided further.

How does the merge step combine two sorted arrays?

It compares the smallest elements of each subarray and picks the smaller one to build a sorted merged array. See execution_table rows 4, 8, and 12 where merging happens step-by-step.

Why do we merge after both left and right halves are sorted?

Because merging two sorted halves produces a fully sorted array. This is shown in execution_table row 12 where the final merge combines two sorted halves into the full sorted array.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the merged array after merging [27] and [43]?

A [27, 43]

B [43, 27]

C [38, 27, 43]

D [27, 38]

💡 Hint

Check the 'Merge Action' and 'Visual State' columns at step 4 in execution_table

At which step does the merge sort algorithm merge the two halves [3, 9] and [10, 82]?

A Step 10

B Step 11

C Step 8

D Step 12

💡 Hint

Look at the 'Merge Action' column for merging [3, 9] and [10, 82] in execution_table

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

A No merges would happen

B The array would be reversed

C Merges would still happen but no swaps needed

D The algorithm would stop early

💡 Hint

Consider the merge step always combines halves, but if sorted, no element swaps occur

Concept Snapshot

Merge Sort Algorithm:
- Recursively split array into halves until size 1
- 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 is a sorting method that splits an array into smaller parts until each part has one element. Then it merges these parts back together in order, making a sorted array. The process repeats recursively for left and right halves. The key steps are dividing the array, sorting each half, and merging sorted halves. The algorithm stops dividing when subarrays have one element because they are already sorted. During merging, it compares elements from two halves and picks the smaller to build a sorted array. This continues until the full array is merged and sorted. Merge sort is efficient with O(n log n) time and is stable but uses extra space for merging.

Practice

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

easy

A. Swap adjacent elements repeatedly until sorted

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

C. Pick the smallest element and move it to the front repeatedly

D. Build a sorted list by inserting elements one by one

Solution

1. Step 1: Understand the divide and conquer approach

   Merge Sort splits the list into smaller parts to make sorting easier.

2. Step 2: Merge sorted halves

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

3. Final Answer:

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

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 it swaps elements directly without splitting
• Assuming it sorts in one pass

2. Which of the following is the correct way to split a list arr into two halves in Python for merge sort?

easy

A. left = arr[:len(arr)//2+1]; right = arr[len(arr)//2:]

B. left = arr[1:len(arr)//2]; right = arr[len(arr)//2+1:]

C. left = arr[:len(arr)//2]; right = arr[len(arr)//2:]

D. left = arr[:len(arr)/2]; right = arr[len(arr)/2:]

Solution

1. Step 1: Use integer division for slicing

   Python list slicing requires integer indices; len(arr)//2 gives an integer midpoint.

2. Step 2: Slice correctly for left and right halves

   Left half is from start to midpoint (exclusive), right half from midpoint to end.

3. Final Answer:

   left = arr[:len(arr)//2]; right = arr[len(arr)//2:] -> Option C

4. Quick Check:

   Integer division and slicing = left = arr[:len(arr)//2]; right = arr[len(arr)//2:] [OK]

Hint: Use // for integer division in slicing [OK]

Common Mistakes:

• Using single slash / causing float index error
• Incorrect slice ranges skipping elements
• Adding +1 unnecessarily in slicing

3. What will be the output of the following code snippet?

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, 3, 4]

Solution

1. Step 1: Recursively split and sort the list

   The list [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 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 list = [1, 2, 3, 4] [OK]

Hint: Trace splits and merges carefully [OK]

Common Mistakes:

• Confusing merge order causing wrong output
• Not extending remaining elements after main loop
• Mixing up indices i and j

4. Identify the error in this merge function used in merge sort:

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

medium

A. Using 'or' instead of 'and' in while condition causes index errors

B. Missing initialization of result list

C. Appending elements without comparing

D. Not returning the merged list

Solution

1. Step 1: Analyze the while loop condition

   Using 'or' means loop continues even if one list is exhausted, causing index out of range errors.

2. Step 2: Correct condition and handle leftovers

   The condition should be 'and' to compare elements safely, then extend remaining elements after loop.

3. Final Answer:

   Using 'or' instead of 'and' in while condition causes index errors -> Option A

4. Quick Check:

   While condition must be 'and' to avoid errors [OK]

Hint: Use 'and' in loop to avoid index errors [OK]

Common Mistakes:

• Using 'or' causing index out of range
• Not extending leftover elements after loop
• Forgetting to increment indices properly

5. You want to sort a list of tuples [(3, 'c'), (1, 'a'), (2, 'b')] by the first element using merge sort. Which modification is needed in the merge function's comparison?

hard

A. Compare using if left[i][1] < right[j][1]:

B. Use if left[i] < right[j]: without change

C. Convert tuples to strings before comparing

D. Change comparison to if left[i][0] < right[j][0]:

Solution

1. Step 1: Understand tuple comparison

   Tuples compare element-wise, but to sort by first element explicitly, compare left[i][0] and right[j][0].

2. Step 2: Modify merge comparison accordingly

   Change the if condition in merge to compare the first elements of tuples for correct sorting.

3. Final Answer:

   Change comparison to if left[i][0] < right[j][0]: -> Option D

4. Quick Check:

   Compare tuple first elements for sorting [OK]

Hint: Compare tuple elements explicitly by index [OK]

Common Mistakes:

• Comparing whole tuples without index may work but is unclear
• Comparing second element instead of first
• Converting tuples to strings unnecessarily