Merge Sort as Divide and Conquer in DSA Python - Build from Scratch

Merge Sort as Divide and Conquer

📖 Scenario: You are working on a program that sorts a list of numbers to help organize data efficiently. Sorting is like arranging books on a shelf in order, so you can find them quickly.

🎯 Goal: Build a program that uses the merge sort method to sort a list of numbers. Merge sort works by splitting the list into smaller parts, sorting those parts, and then joining them back together in order.

📋 What You'll Learn

Create a list of numbers to sort

Define a helper function to merge two sorted lists

Implement the merge sort function using divide and conquer

Print the sorted list

💡 Why This Matters

🌍 Real World

Sorting is used in many real-world applications like organizing data, searching efficiently, and preparing data for reports.

💼 Career

Understanding merge sort helps in software development roles where efficient data processing and algorithm knowledge are important.

1

Create the list of numbers

Create a list called numbers with these exact values: [38, 27, 43, 3, 9, 82, 10]

DSA Python

# Create the list called numbers with the given values
# Your code here

Hint

Use square brackets [] to create the list and separate numbers with commas.

2

Define the merge helper function

Define a function called merge that takes two sorted lists named left and right and returns a single sorted list by combining them.

DSA Python

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

# Define the merge function below
# Your code here

Hint

Use two pointers i and j to track positions in left and right. Compare elements and add the smaller one to result.

3

Implement the merge sort function

Define a function called merge_sort that takes a list called arr. If the list has 1 or 0 elements, return it. Otherwise, split arr into two halves, call merge_sort recursively on each half, and return the merged result using the merge function.

DSA Python

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

def merge(left, right):
    result = []
    i = 0
    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

# Define the merge_sort function below
# Your code here

Hint

Use recursion to split the list until it has 1 or 0 elements, then merge back using the merge function.

4

Print the sorted list

Call the merge_sort function with the numbers list and print the result.

DSA Python

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

def merge(left, right):
    result = []
    i = 0
    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)

# Print the sorted list below
# Your code here

Hint

Call merge_sort(numbers) and print the result to see the sorted list.

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)