Merge Sort as Divide and Conquer in DSA Python

Mental Model

Split the list into smaller parts, sort each part, then join them back in order.

Analogy: Imagine sorting a big pile of cards by splitting them into smaller piles, sorting each small pile, then carefully combining them back into one sorted pile.

Unsorted list:
[38, 27, 43, 3, 9, 82, 10]

Split into halves:
[38, 27, 43]    [3, 9, 82, 10]

Split again:
[38] [27, 43]    [3, 9] [82, 10]

Split until single elements:
[38] [27] [43]    [3] [9] [82] [10]

Dry Run Walkthrough

Input: list: [38, 27, 43, 3, 9, 82, 10]

Goal: Sort the list in ascending order using merge sort

Step 1: Split the list into two halves

[38, 27, 43]    [3, 9, 82, 10]

Why: Divide the problem into smaller parts to make sorting easier

Step 2: Split the left half again

[38]    [27, 43]    [3, 9, 82, 10]

Why: Keep dividing until each part has one element

Step 3: Split the right half into two halves

[38]    [27, 43]    [3, 9]    [82, 10]

Why: Divide the right half to simplify sorting

Step 4: Split [27, 43] into single elements

[38]    [27]    [43]    [3, 9]    [82, 10]

Why: Prepare for merging by having single elements

Step 5: Split [3, 9] into single elements

[38]    [27]    [43]    [3]    [9]    [82, 10]

Why: Prepare for merging by having single elements

Step 6: Split [82, 10] into single elements

[38]    [27]    [43]    [3]    [9]    [82]    [10]

Why: Prepare for merging by having single elements

Step 7: Merge [27] and [43] into sorted [27, 43]

[38]    [27, 43]    [3]    [9]    [82]    [10]

Why: Combine small sorted parts into bigger sorted parts

Step 8: Merge [3] and [9] into sorted [3, 9]

[38]    [27, 43]    [3, 9]    [82]    [10]

Why: Combine small sorted parts into bigger sorted parts

Step 9: Merge [82] and [10] into sorted [10, 82]

[38]    [27, 43]    [3, 9]    [10, 82]

Why: Combine small sorted parts into bigger sorted parts

Step 10: Merge [38] and [27, 43] into sorted [27, 38, 43]

[27, 38, 43]    [3, 9]    [10, 82]

Why: Combine sorted parts to build bigger sorted list

Step 11: Merge [3, 9] and [10, 82] into sorted [3, 9, 10, 82]

[27, 38, 43]    [3, 9, 10, 82]

Why: Combine sorted parts to build bigger sorted list

Step 12: Merge [27, 38, 43] and [3, 9, 10, 82] into fully sorted [3, 9, 10, 27, 38, 43, 82]

[3, 9, 10, 27, 38, 43, 82]

Why: Final merge to get the fully sorted list

Result:

[3, 9, 10, 27, 38, 43, 82]

Annotated Code

DSA Python

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

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])  # add smaller element from left
            i += 1  # move left pointer
        else:
            result.append(right[j])  # add smaller element from right
            j += 1  # move right pointer
    result.extend(left[i:])  # add remaining left elements
    result.extend(right[j:])  # add remaining right elements
    return result

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

if len(arr) <= 1: return arr

base case: list with 0 or 1 element is already sorted

mid = len(arr) // 2

find middle index to split list

left = merge_sort(arr[:mid])

recursively sort left half

right = merge_sort(arr[mid:])

recursively sort right half

return merge(left, right)

merge two sorted halves into one sorted list

while i < len(left) and j < len(right):

compare elements from left and right to merge in order

if left[i] <= right[j]: result.append(left[i]) i += 1

add smaller or equal element from left and move pointer

else: result.append(right[j]) j += 1

add smaller element from right and move pointer

result.extend(left[i:]) result.extend(right[j:])

add any remaining elements after one list is exhausted

Output

[3, 9, 10, 27, 38, 43, 82]

Complexity Analysis

Time: O(n log n) because the list is repeatedly split in half (log n splits) and merging takes linear time at each level

Space: O(n) because extra space is needed to hold merged lists during the process

vs Alternative: Compared to simple sorting like bubble sort with O(n²), merge sort is much faster for large lists due to divide and conquer

Edge Cases

empty list

returns empty list immediately without error

DSA Python

if len(arr) <= 1:
    return arr

list with one element

returns the single element list as sorted

DSA Python

if len(arr) <= 1:
    return arr

list with duplicate elements

duplicates are kept and sorted correctly

DSA Python

if left[i] <= right[j]:

When to Use This Pattern

When you see a problem asking to sort or organize data efficiently, especially large lists, reach for merge sort because it splits the problem into smaller parts and merges them back sorted.

Common Mistakes

Mistake: Forgetting to handle the base case of list length 0 or 1, causing infinite recursion
Fix: Add a base case that returns the list immediately if its length is 0 or 1

Mistake: Merging without comparing elements properly, leading to unsorted results
Fix: Compare elements from both halves and add the smaller one to the result list step by step

Summary

Merge sort splits a list into smaller parts, sorts each, then merges them back in order.

Use it when you need a reliable, efficient sorting method for large lists.

The key insight is dividing the problem into smaller sorted pieces and combining them carefully.

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)