Merge Sort 25 XP Medium

Ctrl+Enter Run Ctrl+S Save

Merge Sort is the gold standard of sorting algorithms — fast, stable, and predictable. Used by Python's built-in sort! 🏆

💡 Think of it like this: To sort a deck of cards, split it into two halves, sort each half separately, then merge them back together by comparing the top cards of each pile.

The Strategy — Divide and Conquer:

1️⃣ Divide: Split the array in half
2️⃣ Conquer: Recursively sort each half
3️⃣ Merge: Combine two sorted halves into one sorted array

💭 Now it's your turn! Using the approach above, implement your solution in the editor. You've got this! 💪

Trace for [38, 27, 43, 10]:

Split: [38, 27] and [43, 10]
Split: [38] [27] and [43] [10]
Merge: [27, 38] and [10, 43]
Merge: [10, 27, 38, 43] ✓

Complexity: Time O(n log n) always — no worst case surprise! Space O(n) for temporary arrays. This is why it's preferred for linked lists and external sorting.

📋 Instructions

Implement `merge_sort(arr)` using recursion and a merge helper. Sort `[38, 27, 43, 3, 9, 82, 10]` and print the result.

Base case: array of length <= 1 is sorted. Split at mid. Recursively sort left and right. Merge by comparing elements from both halves one by one.

⚠️ Try solving it yourself first — you'll learn more!

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])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])   # Add remaining
    result.extend(right[j:])
    return result

🧪 Test Cases

Input

merge_sort([38, 27, 43, 3, 9, 82, 10])

Expected

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

Test case 1

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›