Common Algorithms

Merge Sort

Large-scale data processing requires sorting algorithms with predictable, efficient performance. Merge sort guarantees O(n log n) time complexity regardless of input order, making it the algorithm of choice for sorting large datasets, external files, and situations where consistent performance is critical.

Merge sort is a divide-and-conquer algorithm that divides the list into halves, recursively sorts each half, and then merges the sorted halves.

Algorithm

  1. Divide the list into two halves
  2. Recursively sort each half
  3. Merge the two sorted halves
divide_conquer_sort Split the problem into smaller parts, solve each, then combine the solutions

Basic Implementation

numbers
basic.py
Replay: real traced execution (multi-file project)
# Basic merge sort


def merge_sort(arr):
    """Merge sort implementation"""
    # Base case: single element is sorted
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # Recursively sort
    left = merge_sort(left)
    right = merge_sort(right)

    # Merge sorted halves
    return merge(left, right)


def merge(left, right):
    """Merge two sorted lists"""
    result = []
    i = j = 0

    # Compare and merge
    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

    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])

    return result


# Test merge sort
numbers = [38, 27, 43, 3, 9, 82, 10]

print("Before:", numbers)
sorted_numbers = merge_sort(numbers)
print("After: ", sorted_numbers)


# Basic merge sort


def merge_sort(arr):
    """Merge sort implementation"""
    # Base case: single element is sorted
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # Recursively sort
    left = merge_sort(left)
    right = merge_sort(right)

    # Merge sorted halves
    return merge(left, right)


def merge(left, right):
    """Merge two sorted lists"""
    result = []
    i = j = 0

    # Compare and merge
    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

    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])

    return result


# Test merge sort
numbers = [8, 3, 7, 4, 9, 2]

print("Before:", numbers)
sorted_numbers = merge_sort(numbers)
print("After: ", sorted_numbers)


# Basic merge sort


def merge_sort(arr):
    """Merge sort implementation"""
    # Base case: single element is sorted
    if len(arr) <= 1:
        return arr

    # Divide
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]

    # Recursively sort
    left = merge_sort(left)
    right = merge_sort(right)

    # Merge sorted halves
    return merge(left, right)


def merge(left, right):
    """Merge two sorted lists"""
    result = []
    i = j = 0

    # Compare and merge
    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

    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])

    return result


# Test merge sort
numbers = [5, 1, 6]

print("Before:", numbers)
sorted_numbers = merge_sort(numbers)
print("After: ", sorted_numbers)

  1. numbers ← [38, 27, 43, 3, 9, 82, 10]

    44# Test merge sort45numbers→ [38, 27, 43, 3, 9, 82, 10] = [38, 27, 43, 3, 9, 82, 10]46#@numbers=[8, 3, 7, 4, 9, 2], [5, 1, 6]4748print("Before:", numbers[38, 27, 43, 3, 9, 82, 10])49sorted_numbers = merge_sort(numbers[38, 27, 43, 3, 9, 82, 10])50print("After: ", sorted_numbers)
    outputBefore: [38, 27, 43, 3, 9, 82, 10]

  2. mid ← 3, left ← [38, 27, 43], right ← [3, 9, 82, 10]

    pass 1 of 13
    4def merge_sort(arr[38, 27, 43, 3, 9, 82, 10]):5    """Merge sort implementation"""6    # Base case: single element is sorted7    if len(arr) <= 1:8        return arr910    # Divide11    mid→ 3 = len(arr[38, 27, 43, 3, 9, 82, 10]) // 212    left→ [38, 27, 43] = arr[:mid][38, 27, 43]13    right→ [3, 9, 82, 10] = arr[mid:][3, 9, 82, 10]1415    # Recursively sort16    left = merge_sort(left[38, 27, 43])17    right = merge_sort(right)
    13 passes — pass 1 is the card above
    passarrarr[:mid]arr[mid:]midleftright
    1[38, 27, 43, 3, 9, 82, 10][38, 27, 43][3, 9, 82, 10]3[38, 27, 43][3, 9, 82, 10]
    2[38, 27, 43][38][27, 43]1[38][27, 43]
    3[38]—————
    4[27, 43][27][43]1[27][43]
    5[27]—————
    6[43]—————
    7[3, 9, 82, 10][3, 9][82, 10]2[3, 9][82, 10]
    8[3, 9][3][9]1[3][9]
    9[3]—————
    ⋯ 2 more passes ⋯
    12[82]—————
    13[10]—————

  3. if len(arr) <= 1:

    pass 1 of 7
    6# Base case: single element is sorted7if len(arr[38]) <= 1:8    return arr[38]
    All 7 passes — pass 1 is the card above
    passarr
    1[38]
    2[27]
    3[43]
    4[3]
    5[9]
    6[82]
    7[10]

  4. left ← [38]

    15# Recursively sort16left→ [38] = merge_sort(left)17right = merge_sort(right[27, 43])

  5. left ← [27]

    15# Recursively sort16left→ [27] = merge_sort(left)17right = merge_sort(right[43])

  6. right ← [43]

    16left = merge_sort(left)17right→ [43] = merge_sort(right)1819# Merge sorted halves20return merge(left[27], right[43])

  7. result ← [], i ← 0, j ← 0

    pass 1 of 6
    23def merge(left[27], right[43]):24    """Merge two sorted lists"""25    result→ [] = []26    i→ 0 = j→ 0 = 0
    All 6 passes — pass 1 is the card above
    passleftrightresultij
    1[27][43][]00
    2[38][27, 43][]00
    3[3][9][]00
    4[82][10][]00
    5[3, 9][10, 82][]00
    6[27, 38, 43][3, 9, 10, 82][]00

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

    pass 1 of 13
    28# Compare and merge29while i0 < len(left[27]) and j0 < len(right[43]):30    if left[i] <= right[j]:31        result.append(left[i])
    13 passes — pass 1 is the card above
    passileftjright
    10[27]0[43]
    20[38]0[27, 43]
    30[38]1[27, 43]
    40[3]0[9]
    50[82]0[10]
    60[3, 9]0[10, 82]
    71[3, 9]0[10, 82]
    80[27, 38, 43]0[3, 9, 10, 82]
    90[27, 38, 43]1[3, 9, 10, 82]
    ⋯ 2 more passes ⋯
    121[27, 38, 43]3[3, 9, 10, 82]
    132[27, 38, 43]3[3, 9, 10, 82]

  9. result ← [27], i ← 1

    pass 1 of 8
    29while i < len(left) and j < len(right):30    if left[i]27 <= right[j]43:31        result→ [27].append(left[i]27)32        i→ 1 += 133    else:
    All 8 passes — pass 1 is the card above
    passleft[i]right[j]resulti
    12743[] → [27]0 → 1
    23843[27] → [27, 38]0 → 1
    339[] → [3]0 → 1
    4310[] → [3]0 → 1
    5910[3] → [3, 9]1 → 2
    62782[3, 9, 10] → [3, 9, 10, 27]0 → 1
    73882[3, 9, 10, 27] → [3, 9, 10, 27, 38]1 → 2
    84382[3, 9, 10, 27, 38] → [3, 9, 10, 27, 38, 43]2 → 3

  10. result ← [27, 43]

    37# Add remaining elements38result[27].extend(left[i:][])39result→ [27, 43].extend(right[j:][43])4041return result[27, 43]

  11. right ← [27, 43]

    16left = merge_sort(left)17right→ [27, 43] = merge_sort(right)1819# Merge sorted halves20return merge(left[38], right[27, 43])

  12. result ← [27], j ← 1

    pass 1 of 5
    31    result.append(left[i])32    i += 133else:34    result→ [27].append(right[j]27)35    j→ 1 += 1
    All 5 passes — pass 1 is the card above
    passright[j]resultj
    127[] → [27]0 → 1
    210[] → [10]0 → 1
    33[] → [3]0 → 1
    49[3] → [3, 9]1 → 2
    510[3, 9] → [3, 9, 10]2 → 3

  13. result ← [27, 38, 43]

    37# Add remaining elements38result[27, 38].extend(left[i:][])39result→ [27, 38, 43].extend(right[j:][43])4041return result[27, 38, 43]

  14. left ← [27, 38, 43]

    15# Recursively sort16left→ [27, 38, 43] = merge_sort(left)17right = merge_sort(right[3, 9, 82, 10])

  15. left ← [3]

    15# Recursively sort16left→ [3] = merge_sort(left)17right = merge_sort(right[9])

  16. right ← [9]

    16left = merge_sort(left)17right→ [9] = merge_sort(right)1819# Merge sorted halves20return merge(left[3], right[9])

  17. result ← [3, 9]

    37# Add remaining elements38result[3].extend(left[i:][])39result→ [3, 9].extend(right[j:][9])4041return result[3, 9]

  18. left ← [3, 9]

    15# Recursively sort16left→ [3, 9] = merge_sort(left)17right = merge_sort(right[82, 10])

  19. left ← [82]

    15# Recursively sort16left→ [82] = merge_sort(left)17right = merge_sort(right[10])

  20. right ← [10]

    16left = merge_sort(left)17right→ [10] = merge_sort(right)1819# Merge sorted halves20return merge(left[82], right[10])

  21. result ← [10, 82]

    37# Add remaining elements38result→ [10, 82].extend(left[i:][82])39result[10, 82].extend(right[j:][])4041return result[10, 82]

  22. right ← [10, 82]

    16left = merge_sort(left)17right→ [10, 82] = merge_sort(right)1819# Merge sorted halves20return merge(left[3, 9], right[10, 82])

  23. result ← [3, 9, 10, 82]

    37# Add remaining elements38result[3, 9].extend(left[i:][])39result→ [3, 9, 10, 82].extend(right[j:][10, 82])4041return result[3, 9, 10, 82]

  24. right ← [3, 9, 10, 82]

    16left = merge_sort(left)17right→ [3, 9, 10, 82] = merge_sort(right)1819# Merge sorted halves20return merge(left[27, 38, 43], right[3, 9, 10, 82])

  25. result ← [3, 9, 10, 27, 38, 43, 82]

    37# Add remaining elements38result[3, 9, 10, 27, 38, 43].extend(left[i:][])39result→ [3, 9, 10, 27, 38, 43, 82].extend(right[j:][82])4041return result[3, 9, 10, 27, 38, 43, 82]

  26. sorted_numbers ← [3, 9, 10, 27, 38, 43, 82]

    48print("Before:", numbers)49sorted_numbers→ [3, 9, 10, 27, 38, 43, 82] = merge_sort(numbers[38, 27, 43, 3, 9, 82, 10])50print("After: ", sorted_numbers[3, 9, 10, 27, 38, 43, 82])
    outputAfter:  [3, 9, 10, 27, 38, 43, 82]

  1. numbers ← [8, 3, 7, 4, 9, 2]

    44# Test merge sort45numbers→ [8, 3, 7, 4, 9, 2] = [8, 3, 7, 4, 9, 2]4647print("Before:", numbers[8, 3, 7, 4, 9, 2])48sorted_numbers = merge_sort(numbers[8, 3, 7, 4, 9, 2])49print("After: ", sorted_numbers)
    outputBefore: [8, 3, 7, 4, 9, 2]

  2. mid ← 3, left ← [8, 3, 7], right ← [4, 9, 2]

    pass 1 of 11
    4def merge_sort(arr[8, 3, 7, 4, 9, 2]):5    """Merge sort implementation"""6    # Base case: single element is sorted7    if len(arr) <= 1:8        return arr910    # Divide11    mid→ 3 = len(arr[8, 3, 7, 4, 9, 2]) // 212    left→ [8, 3, 7] = arr[:mid][8, 3, 7]13    right→ [4, 9, 2] = arr[mid:][4, 9, 2]1415    # Recursively sort16    left = merge_sort(left[8, 3, 7])17    right = merge_sort(right)
    All 11 passes — pass 1 is the card above
    passarrarr[:mid]arr[mid:]midleftright
    1[8, 3, 7, 4, 9, 2][8, 3, 7][4, 9, 2]3[8, 3, 7][4, 9, 2]
    2[8, 3, 7][8][3, 7]1[8][3, 7]
    3[8]—————
    4[3, 7][3][7]1[3][7]
    5[3]—————
    6[7]—————
    7[4, 9, 2][4][9, 2]1[4][9, 2]
    8[4]—————
    9[9, 2][9][2]1[9][2]
    10[9]—————
    11[2]—————

  3. if len(arr) <= 1:

    pass 1 of 6
    6# Base case: single element is sorted7if len(arr[8]) <= 1:8    return arr[8]
    All 6 passes — pass 1 is the card above
    passarr
    1[8]
    2[3]
    3[7]
    4[4]
    5[9]
    6[2]

  4. left ← [8]

    15# Recursively sort16left→ [8] = merge_sort(left)17right = merge_sort(right[3, 7])

  5. left ← [3]

    15# Recursively sort16left→ [3] = merge_sort(left)17right = merge_sort(right[7])

  6. right ← [7]

    16left = merge_sort(left)17right→ [7] = merge_sort(right)1819# Merge sorted halves20return merge(left[3], right[7])

  7. result ← [], i ← 0, j ← 0

    pass 1 of 5
    23def merge(left[3], right[7]):24    """Merge two sorted lists"""25    result→ [] = []26    i→ 0 = j→ 0 = 0
    All 5 passes — pass 1 is the card above
    passleftrightresultij
    1[3][7][]00
    2[8][3, 7][]00
    3[9][2][]00
    4[4][2, 9][]00
    5[3, 7, 8][2, 4, 9][]00

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

    pass 1 of 11
    28# Compare and merge29while i0 < len(left[3]) and j0 < len(right[7]):30    if left[i] <= right[j]:31        result.append(left[i])
    All 11 passes — pass 1 is the card above
    passileftjright
    10[3]0[7]
    20[8]0[3, 7]
    30[8]1[3, 7]
    40[9]0[2]
    50[4]0[2, 9]
    60[4]1[2, 9]
    70[3, 7, 8]0[2, 4, 9]
    80[3, 7, 8]1[2, 4, 9]
    91[3, 7, 8]1[2, 4, 9]
    101[3, 7, 8]2[2, 4, 9]
    112[3, 7, 8]2[2, 4, 9]

  9. result ← [3], i ← 1

    pass 1 of 5
    29while i < len(left) and j < len(right):30    if left[i]3 <= right[j]7:31        result→ [3].append(left[i]3)32        i→ 1 += 133    else:
    All 5 passes — pass 1 is the card above
    passleft[i]right[j]resulti
    137[] → [3]0 → 1
    249[2] → [2, 4]0 → 1
    334[2] → [2, 3]0 → 1
    479[2, 3, 4] → [2, 3, 4, 7]1 → 2
    589[2, 3, 4, 7] → [2, 3, 4, 7, 8]2 → 3

  10. result ← [3, 7]

    37# Add remaining elements38result[3].extend(left[i:][])39result→ [3, 7].extend(right[j:][7])4041return result[3, 7]

  11. right ← [3, 7]

    16left = merge_sort(left)17right→ [3, 7] = merge_sort(right)1819# Merge sorted halves20return merge(left[8], right[3, 7])

  12. result ← [3], j ← 1

    pass 1 of 6
    31    result.append(left[i])32    i += 133else:34    result→ [3].append(right[j]3)35    j→ 1 += 1
    All 6 passes — pass 1 is the card above
    passright[j]resultj
    13[] → [3]0 → 1
    27[3] → [3, 7]1 → 2
    32[] → [2]0 → 1
    42[] → [2]0 → 1
    52[] → [2]0 → 1
    64[2, 3] → [2, 3, 4]1 → 2

  13. result ← [3, 7, 8]

    37# Add remaining elements38result→ [3, 7, 8].extend(left[i:][8])39result[3, 7, 8].extend(right[j:][])4041return result[3, 7, 8]

  14. left ← [3, 7, 8]

    15# Recursively sort16left→ [3, 7, 8] = merge_sort(left)17right = merge_sort(right[4, 9, 2])

  15. left ← [4]

    15# Recursively sort16left→ [4] = merge_sort(left)17right = merge_sort(right[9, 2])

  16. left ← [9]

    15# Recursively sort16left→ [9] = merge_sort(left)17right = merge_sort(right[2])

  17. right ← [2]

    16left = merge_sort(left)17right→ [2] = merge_sort(right)1819# Merge sorted halves20return merge(left[9], right[2])

  18. result ← [2, 9]

    37# Add remaining elements38result→ [2, 9].extend(left[i:][9])39result[2, 9].extend(right[j:][])4041return result[2, 9]

  19. right ← [2, 9]

    16left = merge_sort(left)17right→ [2, 9] = merge_sort(right)1819# Merge sorted halves20return merge(left[4], right[2, 9])

  20. result ← [2, 4, 9]

    37# Add remaining elements38result[2, 4].extend(left[i:][])39result→ [2, 4, 9].extend(right[j:][9])4041return result[2, 4, 9]

  21. right ← [2, 4, 9]

    16left = merge_sort(left)17right→ [2, 4, 9] = merge_sort(right)1819# Merge sorted halves20return merge(left[3, 7, 8], right[2, 4, 9])

  22. result ← [2, 3, 4, 7, 8, 9]

    37# Add remaining elements38result[2, 3, 4, 7, 8].extend(left[i:][])39result→ [2, 3, 4, 7, 8, 9].extend(right[j:][9])4041return result[2, 3, 4, 7, 8, 9]

  23. sorted_numbers ← [2, 3, 4, 7, 8, 9]

    47print("Before:", numbers)48sorted_numbers→ [2, 3, 4, 7, 8, 9] = merge_sort(numbers[8, 3, 7, 4, 9, 2])49print("After: ", sorted_numbers[2, 3, 4, 7, 8, 9])
    outputAfter:  [2, 3, 4, 7, 8, 9]

  1. numbers ← [5, 1, 6]

    44# Test merge sort45numbers→ [5, 1, 6] = [5, 1, 6]4647print("Before:", numbers[5, 1, 6])48sorted_numbers = merge_sort(numbers[5, 1, 6])49print("After: ", sorted_numbers)
    outputBefore: [5, 1, 6]

  2. mid ← 1, left ← [5], right ← [1, 6]

    pass 1 of 5
    4def merge_sort(arr[5, 1, 6]):5    """Merge sort implementation"""6    # Base case: single element is sorted7    if len(arr) <= 1:8        return arr910    # Divide11    mid→ 1 = len(arr[5, 1, 6]) // 212    left→ [5] = arr[:mid][5]13    right→ [1, 6] = arr[mid:][1, 6]1415    # Recursively sort16    left = merge_sort(left[5])17    right = merge_sort(right)
    All 5 passes — pass 1 is the card above
    passarrarr[:mid]arr[mid:]midleftright
    1[5, 1, 6][5][1, 6]1[5][1, 6]
    2[5]—————
    3[1, 6][1][6]1[1][6]
    4[1]—————
    5[6]—————

  3. if len(arr) <= 1:

    pass 1 of 3
    6# Base case: single element is sorted7if len(arr[5]) <= 1:8    return arr[5]
    All 3 passes — pass 1 is the card above
    passarr
    1[5]
    2[1]
    3[6]

  4. left ← [5]

    15# Recursively sort16left→ [5] = merge_sort(left)17right = merge_sort(right[1, 6])

  5. left ← [1]

    15# Recursively sort16left→ [1] = merge_sort(left)17right = merge_sort(right[6])

  6. right ← [6]

    16left = merge_sort(left)17right→ [6] = merge_sort(right)1819# Merge sorted halves20return merge(left[1], right[6])

  7. result ← [], i ← 0, j ← 0

    pass 1 of 2
    23def merge(left[1], right[6]):24    """Merge two sorted lists"""25    result→ [] = []26    i→ 0 = j→ 0 = 0

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

    pass 1 of 3
    28# Compare and merge29while i0 < len(left[1]) and j0 < len(right[6]):30    if left[i] <= right[j]:31        result.append(left[i])
    All 3 passes — pass 1 is the card above
    passleftrightleft[i]right[j]resultij
    1[1][6]16[] → [1]0 → 10
    2[5][1, 6]—1[] → [1]00 → 1
    3[5][1, 6]56[1] → [1, 5]0 → 11

  9. result ← [1], i ← 1

    pass 1 of 2
    29while i < len(left) and j < len(right):30    if left[i]1 <= right[j]6:31        result→ [1].append(left[i]1)32        i→ 1 += 133    else:

  10. result ← [1, 6]

    37# Add remaining elements38result[1].extend(left[i:][])39result→ [1, 6].extend(right[j:][6])4041return result[1, 6]

  11. right ← [1, 6]

    16left = merge_sort(left)17right→ [1, 6] = merge_sort(right)1819# Merge sorted halves20return merge(left[5], right[1, 6])

  12. result ← [], i ← 0, j ← 0

    pass 2 of 2
    23def merge(left[5], right[1, 6]):24    """Merge two sorted lists"""25    result→ [] = []26    i→ 0 = j→ 0 = 0

  13. result ← [1], j ← 1

    31    result.append(left[i])32    i += 133else:34    result→ [1].append(right[j]1)35    j→ 1 += 1

  14. result ← [1, 5], i ← 1

    pass 2 of 2
    29while i < len(left) and j < len(right):30    if left[i]5 <= right[j]6:31        result→ [1, 5].append(left[i]5)32        i→ 1 += 133    else:

  15. result ← [1, 5, 6]

    37# Add remaining elements38result[1, 5].extend(left[i:][])39result→ [1, 5, 6].extend(right[j:][6])4041return result[1, 5, 6]

  16. sorted_numbers ← [1, 5, 6]

    47print("Before:", numbers)48sorted_numbers→ [1, 5, 6] = merge_sort(numbers[5, 1, 6])49print("After: ", sorted_numbers[1, 5, 6])
    outputAfter:  [1, 5, 6]

The Merge Operation

merge_only.py
Replay: real traced execution (multi-file project)
# Merge two sorted lists


def merge_two_sorted(left, right):
    """Merge two already sorted lists"""
    result = []
    i = j = 0

    # Compare and merge
    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

    # Add remaining elements
    result.extend(left[i:])
    result.extend(right[j:])

    return result


# Test merging sorted lists
left = [1, 3, 5, 7]
right = [2, 4, 6, 8]

print("Left: ", left)
print("Right:", right)

merged = merge_two_sorted(left, right)
print("Merged:", merged)

# Different sizes
arr1 = [1, 5, 9]
arr2 = [2, 3, 4, 6, 7]

print("\nLeft: ", arr1)
print("Right:", arr2)

merged2 = merge_two_sorted(arr1, arr2)
print("Merged:", merged2)

  1. left ← [1, 3, 5, 7], right ← [2, 4, 6, 8]

    25# Test merging sorted lists26left→ [1, 3, 5, 7] = [1, 3, 5, 7]27right→ [2, 4, 6, 8] = [2, 4, 6, 8]2829print("Left: ", left[1, 3, 5, 7])30print("Right:", right[2, 4, 6, 8])3132merged = merge_two_sorted(left[1, 3, 5, 7], right[2, 4, 6, 8])33print("Merged:", merged)
    outputLeft:  [1, 3, 5, 7]
Right: [2, 4, 6, 8]

  2. result ← [], i ← 0, j ← 0

    pass 1 of 2
    4def merge_two_sorted(left[1, 3, 5, 7], right[2, 4, 6, 8]):5    """Merge two already sorted lists"""6    result→ [] = []7    i→ 0 = j→ 0 = 0

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

    pass 1 of 14
    9# Compare and merge10while i0 < len(left[1, 3, 5, 7]) and j0 < len(right[2, 4, 6, 8]):11    if left[i] <= right[j]:12        result.append(left[i])
    14 passes — pass 1 is the card above
    passileftjright
    10[1, 3, 5, 7]0[2, 4, 6, 8]
    21[1, 3, 5, 7]0[2, 4, 6, 8]
    31[1, 3, 5, 7]1[2, 4, 6, 8]
    42[1, 3, 5, 7]1[2, 4, 6, 8]
    52[1, 3, 5, 7]2[2, 4, 6, 8]
    63[1, 3, 5, 7]2[2, 4, 6, 8]
    73[1, 3, 5, 7]3[2, 4, 6, 8]
    80[1, 5, 9]0[2, 3, 4, 6, 7]
    91[1, 5, 9]0[2, 3, 4, 6, 7]
    ⋯ 3 more passes ⋯
    132[1, 5, 9]3[2, 3, 4, 6, 7]
    142[1, 5, 9]4[2, 3, 4, 6, 7]

  4. result ← [1], i ← 1

    pass 1 of 6
    10while i < len(left) and j < len(right):11    if left[i]1 <= right[j]2:12        result→ [1].append(left[i]1)13        i→ 1 += 114    else:
    All 6 passes — pass 1 is the card above
    passleft[i]right[j]resulti
    112[] → [1]0 → 1
    234[1, 2] → [1, 2, 3]1 → 2
    356[1, 2, 3, 4] → [1, 2, 3, 4, 5]2 → 3
    478[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]3 → 4
    512[] → [1]0 → 1
    656[1, 2, 3, 4] → [1, 2, 3, 4, 5]1 → 2

  5. result ← [1, 2], j ← 1

    pass 1 of 8
    12    result.append(left[i])13    i += 114else:15    result→ [1, 2].append(right[j]2)16    j→ 1 += 1
    All 8 passes — pass 1 is the card above
    passright[j]resultj
    12[1] → [1, 2]0 → 1
    24[1, 2, 3] → [1, 2, 3, 4]1 → 2
    36[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]2 → 3
    42[1] → [1, 2]0 → 1
    53[1, 2] → [1, 2, 3]1 → 2
    64[1, 2, 3] → [1, 2, 3, 4]2 → 3
    76[1, 2, 3, 4, 5] → [1, 2, 3, 4, 5, 6]3 → 4
    87[1, 2, 3, 4, 5, 6] → [1, 2, 3, 4, 5, 6, 7]4 → 5

  6. result ← [1, 2, 3, 4, 5, 6, 7, 8]

    18# Add remaining elements19result[1, 2, 3, 4, 5, 6, 7].extend(left[i:][])20result→ [1, 2, 3, 4, 5, 6, 7, 8].extend(right[j:][8])2122return result[1, 2, 3, 4, 5, 6, 7, 8]

  7. merged ← [1, 2, 3, 4, 5, 6, 7, 8], arr1 ← [1, 5, 9], arr2 ← [2, 3, 4, 6, 7]

    32merged→ [1, 2, 3, 4, 5, 6, 7, 8] = merge_two_sorted(left[1, 3, 5, 7], right[2, 4, 6, 8])33print("Merged:", merged[1, 2, 3, 4, 5, 6, 7, 8])3435# Different sizes36arr1→ [1, 5, 9] = [1, 5, 9]37arr2→ [2, 3, 4, 6, 7] = [2, 3, 4, 6, 7]3839print("\nLeft: ", arr1[1, 5, 9])40print("Right:", arr2[2, 3, 4, 6, 7])4142merged2 = merge_two_sorted(arr1[1, 5, 9], arr2[2, 3, 4, 6, 7])43print("Merged:", merged2)
    outputMerged: [1, 2, 3, 4, 5, 6, 7, 8]

Left:  [1, 5, 9]
Right: [2, 3, 4, 6, 7]

  8. result ← [], i ← 0, j ← 0

    pass 2 of 2
    4def merge_two_sorted(left[1, 5, 9], right[2, 3, 4, 6, 7]):5    """Merge two already sorted lists"""6    result→ [] = []7    i→ 0 = j→ 0 = 0

  9. result ← [1, 2, 3, 4, 5, 6, 7, 9]

    18# Add remaining elements19result→ [1, 2, 3, 4, 5, 6, 7, 9].extend(left[i:][9])20result[1, 2, 3, 4, 5, 6, 7, 9].extend(right[j:][])2122return result[1, 2, 3, 4, 5, 6, 7, 9]

  10. merged2 ← [1, 2, 3, 4, 5, 6, 7, 9]

    42merged2→ [1, 2, 3, 4, 5, 6, 7, 9] = merge_two_sorted(arr1[1, 5, 9], arr2[2, 3, 4, 6, 7])43print("Merged:", merged2[1, 2, 3, 4, 5, 6, 7, 9])
    outputMerged: [1, 2, 3, 4, 5, 6, 7, 9]
merge_operation Combine two sorted lists into one sorted list by comparing front elements

Trace Example

trace.py
Replay: real traced execution (multi-file project)
# Merge sort with trace


depth = 0


def merge_sort_trace(arr):
    """Merge sort with step-by-step trace"""
    global depth

    if len(arr) <= 1:
        return arr

    # Trace divide
    print("  " * depth + f"Divide: {arr}")
    depth += 1

    mid = len(arr) // 2
    left = merge_sort_trace(arr[:mid])
    right = merge_sort_trace(arr[mid:])

    result = merge_trace(left, right)

    depth -= 1
    print("  " * depth + f"Merged: {result}")

    return result


def merge_trace(left, right):
    """Merge with trace"""
    global depth
    print("  " * depth + f"  Merge {left} and {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


# Test with trace
numbers = [5, 2, 8, 1, 9]

print("Initial:", numbers)
print()
sorted_numbers = merge_sort_trace(numbers)
print()
print("Final:  ", sorted_numbers)

  1. depth ← 0, numbers ← [5, 2, 8, 1, 9]

    4depth→ 0 = 0567def merge_sort_trace(arr):8    """Merge sort with step-by-step trace"""9    global depth1011    if len(arr) <= 1:12        return arr1314    # Trace divide15    print("  " * depth + f"Divide: {arr}")16    depth += 11718    mid = len(arr) // 219    left = merge_sort_trace(arr[:mid])20    right = merge_sort_trace(arr[mid:])2122    result = merge_trace(left, right)2324    depth -= 125    print("  " * depth + f"Merged: {result}")2627    return result282930def merge_trace(left, right):31    """Merge with trace"""32    global depth33    print("  " * depth + f"  Merge {left} and {right}")3435    result = []36    i = j = 03738    while i < len(left) and j < len(right):39        if left[i] <= right[j]:40            result.append(left[i])41            i += 142        else:43            result.append(right[j])44            j += 14546    result.extend(left[i:])47    result.extend(right[j:])4849    return result505152# Test with trace53numbers→ [5, 2, 8, 1, 9] = [5, 2, 8, 1, 9]5455print("Initial:", numbers[5, 2, 8, 1, 9])56print()57sorted_numbers = merge_sort_trace(numbers[5, 2, 8, 1, 9])58print()
    outputInitial: [5, 2, 8, 1, 9]

  2. depth ← 1, mid ← 2

    pass 1 of 9
    7def merge_sort_trace(arr[5, 2, 8, 1, 9]):8    """Merge sort with step-by-step trace"""9    global depth1011    if len(arr) <= 1:12        return arr1314    # Trace divide15    print("  " * depth0 + f"Divide: {arr[5, 2, 8, 1, 9]}")16    depth→ 1 += 11718    mid→ 2 = len(arr[5, 2, 8, 1, 9]) // 219    left = merge_sort_trace(arr[:mid][5, 2])20    right = merge_sort_trace(arr[mid:])
    outputDivide: [5, 2, 8, 1, 9]
    All 9 passes — pass 1 is the card above
    passarrarr[:mid]depthmid
    1[5, 2, 8, 1, 9][5, 2]0 → 12
    2[5, 2][5]1 → 21
    3[5]———
    4[2]———
    5[8, 1, 9][8]1 → 21
    6[8]———
    7[1, 9][1]2 → 31
    8[1]———
    9[9]———

  3. if len(arr) <= 1:

    pass 1 of 5
    11if len(arr[5]) <= 1:12    return arr[5]
    All 5 passes — pass 1 is the card above
    passarr
    1[5]
    2[2]
    3[8]
    4[1]
    5[9]

  4. left ← [5]

    18mid = len(arr) // 219left→ [5] = merge_sort_trace(arr[:mid][5])20right = merge_sort_trace(arr[mid:][2])

  5. right ← [2]

    19left = merge_sort_trace(arr[:mid])20right→ [2] = merge_sort_trace(arr[mid:][2])2122result = merge_trace(left[5], right[2])

  6. result ← [], i ← 0, j ← 0

    pass 1 of 4
    30def merge_trace(left[5], right[2]):31    """Merge with trace"""32    global depth33    print("  " * depth2 + f"  Merge {left[5]} and {right[2]}")3435    result→ [] = []36    i→ 0 = j→ 0 = 0
    output      Merge [5] and [2]
    All 4 passes — pass 1 is the card above
    passleftrightdepthresultij
    1[5][2]2[]00
    2[1][9]3[]00
    3[8][1, 9]2[]00
    4[2, 5][1, 8, 9]1[]00

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

    pass 1 of 7
    38while i0 < len(left[5]) and j0 < len(right[2]):39    if left[i] <= right[j]:40        result.append(left[i])
    All 7 passes — pass 1 is the card above
    passileftjright
    10[5]0[2]
    20[1]0[9]
    30[8]0[1, 9]
    40[8]1[1, 9]
    50[2, 5]0[1, 8, 9]
    60[2, 5]1[1, 8, 9]
    71[2, 5]1[1, 8, 9]

  8. result ← [2], j ← 1

    pass 1 of 3
    40    result.append(left[i])41    i += 142else:43    result→ [2].append(right[j]2)44    j→ 1 += 1
    All 3 passes — pass 1 is the card above
    passright[j]resultj
    12[] → [2]0 → 1
    21[] → [1]0 → 1
    31[] → [1]0 → 1

  9. result ← [2, 5]

    46result→ [2, 5].extend(left[i:][5])47result[2, 5].extend(right[j:][])4849return result[2, 5]

  10. result ← [2, 5], depth ← 1

    22result→ [2, 5] = merge_trace(left[5], right[2])2324depth→ 1 -= 125print("  " * depth1 + f"Merged: {result[2, 5]}")2627return result[2, 5]
    output  Merged: [2, 5]

  11. arr[:mid] ← [5, 2], left ← [2, 5]

    18mid = len(arr) // 219left→ [2, 5] = merge_sort_trace(arr[:mid]→ [5, 2])20right = merge_sort_trace(arr[mid:][8, 1, 9])

  12. left ← [8]

    18mid = len(arr) // 219left→ [8] = merge_sort_trace(arr[:mid][8])20right = merge_sort_trace(arr[mid:][1, 9])

  13. left ← [1]

    18mid = len(arr) // 219left→ [1] = merge_sort_trace(arr[:mid][1])20right = merge_sort_trace(arr[mid:][9])

  14. right ← [9]

    19left = merge_sort_trace(arr[:mid])20right→ [9] = merge_sort_trace(arr[mid:][9])2122result = merge_trace(left[1], right[9])

  15. result ← [1], i ← 1

    pass 1 of 4
    38while i < len(left) and j < len(right):39    if left[i]1 <= right[j]9:40        result→ [1].append(left[i]1)41        i→ 1 += 142    else:
    All 4 passes — pass 1 is the card above
    passleft[i]right[j]resulti
    119[] → [1]0 → 1
    289[1] → [1, 8]0 → 1
    328[1] → [1, 2]0 → 1
    458[1, 2] → [1, 2, 5]1 → 2

  16. result ← [1, 9]

    46result[1].extend(left[i:][])47result→ [1, 9].extend(right[j:][9])4849return result[1, 9]

  17. result ← [1, 9], depth ← 2

    22result→ [1, 9] = merge_trace(left[1], right[9])2324depth→ 2 -= 125print("  " * depth2 + f"Merged: {result[1, 9]}")2627return result[1, 9]
    output    Merged: [1, 9]

  18. arr[mid:] ← [1, 9], right ← [1, 9]

    19left = merge_sort_trace(arr[:mid])20right→ [1, 9] = merge_sort_trace(arr[mid:]→ [1, 9])2122result = merge_trace(left[8], right[1, 9])

  19. result ← [1, 8, 9]

    46result[1, 8].extend(left[i:][])47result→ [1, 8, 9].extend(right[j:][9])4849return result[1, 8, 9]

  20. result ← [1, 8, 9], depth ← 1

    22result→ [1, 8, 9] = merge_trace(left[8], right[1, 9])2324depth→ 1 -= 125print("  " * depth1 + f"Merged: {result[1, 8, 9]}")2627return result[1, 8, 9]
    output  Merged: [1, 8, 9]

  21. arr[mid:] ← [8, 1, 9], right ← [1, 8, 9]

    19left = merge_sort_trace(arr[:mid])20right→ [1, 8, 9] = merge_sort_trace(arr[mid:]→ [8, 1, 9])2122result = merge_trace(left[2, 5], right[1, 8, 9])

  22. result ← [1, 2, 5, 8, 9]

    46result[1, 2, 5].extend(left[i:][])47result→ [1, 2, 5, 8, 9].extend(right[j:][8, 9])4849return result[1, 2, 5, 8, 9]

  23. result ← [1, 2, 5, 8, 9], depth ← 0

    22result→ [1, 2, 5, 8, 9] = merge_trace(left[2, 5], right[1, 8, 9])2324depth→ 0 -= 125print("  " * depth0 + f"Merged: {result[1, 2, 5, 8, 9]}")2627return result[1, 2, 5, 8, 9]
    outputMerged: [1, 2, 5, 8, 9]

  24. sorted_numbers ← [1, 2, 5, 8, 9]

    56print()57sorted_numbers→ [1, 2, 5, 8, 9] = merge_sort_trace(numbers[5, 2, 8, 1, 9])58print()59print("Final:  ", sorted_numbers[1, 2, 5, 8, 9])
    outputFinal:   [1, 2, 5, 8, 9]

In-Place Variation

inplace.py
Replay: real traced execution (multi-file project)
# In-place merge sort


def merge_sort_inplace(arr, left=0, right=None):
    """Merge sort that modifies array in place"""
    if right is None:
        right = len(arr) - 1

    # Divide and conquer
    if left < right:
        mid = left + (right - left) // 2

        merge_sort_inplace(arr, left, mid)
        merge_sort_inplace(arr, mid + 1, right)

        merge_inplace(arr, left, mid, right)


def merge_inplace(arr, left, mid, right):
    """Merge in place using temporary list"""
    # Create temporary arrays
    left_arr = arr[left:mid + 1]
    right_arr = arr[mid + 1:right + 1]

    # Merge back into original
    i = j = 0
    k = left

    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] <= right_arr[j]:
            arr[k] = left_arr[i]
            i += 1
        else:
            arr[k] = right_arr[j]
            j += 1
        k += 1

    # Copy remaining
    while i < len(left_arr):
        arr[k] = left_arr[i]
        i += 1
        k += 1

    while j < len(right_arr):
        arr[k] = right_arr[j]
        j += 1
        k += 1


# Test in-place version
numbers = [38, 27, 43, 3, 9, 82, 10]

print("Before:", numbers)
merge_sort_inplace(numbers)
print("After: ", numbers)

  1. numbers ← [38, 27, 43, 3, 9, 82, 10]

    50# Test in-place version51numbers→ [38, 27, 43, 3, 9, 82, 10] = [38, 27, 43, 3, 9, 82, 10]5253print("Before:", numbers[38, 27, 43, 3, 9, 82, 10])54merge_sort_inplace(numbers[38, 27, 43, 3, 9, 82, 10])55print("After: ", numbers)
    outputBefore: [38, 27, 43, 3, 9, 82, 10]

  2. def merge_sort_inplace(arr, left=0, right=None):

    pass 1 of 13
    4def merge_sort_inplace(arr[38, 27, 43, 3, 9, 82, 10], left0=0, rightNone=NoneNone):5    """Merge sort that modifies array in place"""6    if right is None:
    13 passes — pass 1 is the card above
    passarrleftmidright
    1[38, 27, 43, 3, 9, 82, 10]0—None → 6
    2[38, 27, 43, 3, 9, 82, 10]0—3
    3[38, 27, 43, 3, 9, 82, 10]0—1
    4[38, 27, 43, 3, 9, 82, 10]000
    5[38, 27, 43, 3, 9, 82, 10]101
    6[27, 38, 43, 3, 9, 82, 10]2—3
    7[27, 38, 43, 3, 9, 82, 10]222
    8[27, 38, 43, 3, 9, 82, 10]323
    9[3, 27, 38, 43, 9, 82, 10]4—6
    ⋯ 2 more passes ⋯
    12[3, 27, 38, 43, 9, 82, 10]545
    13[3, 27, 38, 43, 9, 82, 10]656

  3. right ← 6

    5"""Merge sort that modifies array in place"""6if rightNone is None:7    right→ 6 = len(arr[38, 27, 43, 3, 9, 82, 10]) - 1

  4. mid ← 3

    pass 1 of 6
    9# Divide and conquer10if left0 < right6:11    mid→ 3 = left0 + (right6 - left) // 21213    merge_sort_inplace(arr[38, 27, 43, 3, 9, 82, 10], left0, mid3)14    merge_sort_inplace(arr, mid + 1, right)
    All 6 passes — pass 1 is the card above
    passleftrightarrmid
    106[38, 27, 43, 3, 9, 82, 10]3
    203[38, 27, 43, 3, 9, 82, 10]1
    301[38, 27, 43, 3, 9, 82, 10]0
    423[27, 38, 43, 3, 9, 82, 10]2
    546[3, 27, 38, 43, 9, 82, 10]5
    645[3, 27, 38, 43, 9, 82, 10]4

  5. left_arr ← [38], right_arr ← [27], i ← 0, j ← 0, k ← 0

    pass 1 of 6
    19def merge_inplace(arr[38, 27, 43, 3, 9, 82, 10], left0, mid0, right1):20    """Merge in place using temporary list"""21    # Create temporary arrays22    left_arr→ [38] = arr[left:mid + 1][38]23    right_arr→ [27] = arr[mid + 1:right + 1][27]2425    # Merge back into original26    i→ 0 = j→ 0 = 027    k→ 0 = left0
    All 6 passes — pass 1 is the card above
    passarrleftmidrightarr[left:mid + 1]arr[mid + 1:right + 1]left_arrright_arrijk
    1[38, 27, 43, 3, 9, 82, 10]001[38][27][38][27]000
    2[27, 38, 43, 3, 9, 82, 10]223[43][3][43][3]002
    3[27, 38, 3, 43, 9, 82, 10]013[27, 38][3, 43][27, 38][3, 43]000
    4[3, 27, 38, 43, 9, 82, 10]445[9][82][9][82]004
    5[3, 27, 38, 43, 9, 82, 10]456[9, 82][10][9, 82][10]004
    6[3, 27, 38, 43, 9, 10, 82]036[3, 27, 38, 43][9, 10, 82][3, 27, 38, 43][9, 10, 82]000

  6. while i < len(left_arr) and j < len(right_arr):

    pass 1 of 14
    29while i0 < len(left_arr[38]) and j0 < len(right_arr[27]):30    if left_arr[i] <= right_arr[j]:31        arr[k] = left_arr[i]
    14 passes — pass 1 is the card above
    passileft_arrjright_arr
    10[38]0[27]
    20[43]0[3]
    30[27, 38]0[3, 43]
    40[27, 38]1[3, 43]
    51[27, 38]1[3, 43]
    60[9]0[82]
    70[9, 82]0[10]
    81[9, 82]0[10]
    90[3, 27, 38, 43]0[9, 10, 82]
    ⋯ 3 more passes ⋯
    132[3, 27, 38, 43]2[9, 10, 82]
    143[3, 27, 38, 43]2[9, 10, 82]

  7. arr[k] ← 27, j ← 1

    pass 1 of 6
    31    arr[k] = left_arr[i]32    i += 133else:34    arr[k]→ 27 = right_arr[j]2735    j→ 1 += 136k += 1
    All 6 passes — pass 1 is the card above
    passright_arr[j]arr[k]j
    127270 → 1
    2330 → 1
    3330 → 1
    410100 → 1
    5990 → 1
    610101 → 2

  8. k ← 1

    35    j += 136k→ 1 += 1

  9. arr[k] ← 38, i ← 1, k ← 2, arr ← [27, 38, 43, 3, 9, 82, 10], left ← 0

    pass 1 of 3
    13        merge_sort_inplace(arr→ [27, 38, 43, 3, 9, 82, 10], left→ 0, mid→ 1)14        merge_sort_inplace(arr[27, 38, 43, 3, 9, 82, 10], mid1 + 1, right3)1516        merge_inplace(arr→ [27, 38, 43, 3, 9, 82, 10], left0, mid0, right1)171819def merge_inplace(arr, left, mid, right):20    """Merge in place using temporary list"""21    # Create temporary arrays22    left_arr = arr[left:mid + 1]23    right_arr = arr[mid + 1:right + 1]2425    # Merge back into original26    i = j = 027    k = left2829    while i < len(left_arr) and j < len(right_arr):30        if left_arr[i] <= right_arr[j]:31            arr[k] = left_arr[i]32            i += 133        else:34            arr[k] = right_arr[j]35            j += 136        k += 13738    # Copy remaining39    while i0 < len(left_arr[38]):40        arr[k]→ 38 = left_arr[i]3841        i→ 1 += 142        k→ 2 += 1
    All 3 passes — pass 1 is the card above
    passleft_arrleft_arr[i]arr[k]ikarrleftmidright
    1[38]38380 → 11 → 2[38, 27, 43, 3, 9, 82, 10] → [27, 38, 43, 3, 9, 82, 10]00 → 11
    2[43]43430 → 13 → 4[27, 38, 43, 3, 9, 82, 10] → [27, 38, 3, 43, 9, 82, 10]013
    3[9, 82]82821 → 26 → 7[3, 27, 38, 43, 9, 82, 10] → [3, 27, 38, 43, 9, 10, 82]036

  10. k ← 3

    35    j += 136k→ 3 += 1

  11. k ← 1

    35    j += 136k→ 1 += 1

  12. arr[k] ← 27, i ← 1

    pass 1 of 8
    29while i < len(left_arr) and j < len(right_arr):30    if left_arr[i]27 <= right_arr[j]43:31        arr[k]→ 27 = left_arr[i]2732        i→ 1 += 133    else:
    All 8 passes — pass 1 is the card above
    passleft_arr[i]right_arr[j]arr[k]i
    12743270 → 1
    23843381 → 2
    398290 → 1
    491090 → 1
    53930 → 1
    62782271 → 2
    73882382 → 3
    84382433 → 4

  13. k ← 2

    35    j += 136k→ 2 += 1

  14. k ← 3

    35    j += 136k→ 3 += 1

  15. arr[k] ← 43, j ← 2, k ← 4, arr ← [3, 27, 38, 43, 9, 82, 10], left ← 0

    pass 1 of 3
    13        merge_sort_inplace(arr→ [3, 27, 38, 43, 9, 82, 10], left→ 0, mid→ 3)14        merge_sort_inplace(arr[3, 27, 38, 43, 9, 82, 10], mid3 + 1, right6)1516        merge_inplace(arr→ [3, 27, 38, 43, 9, 82, 10], left0, mid1, right3)171819def merge_inplace(arr, left, mid, right):20    """Merge in place using temporary list"""21    # Create temporary arrays22    left_arr = arr[left:mid + 1]23    right_arr = arr[mid + 1:right + 1]2425    # Merge back into original26    i = j = 027    k = left2829    while i < len(left_arr) and j < len(right_arr):30        if left_arr[i] <= right_arr[j]:31            arr[k] = left_arr[i]32            i += 133        else:34            arr[k] = right_arr[j]35            j += 136        k += 13738    # Copy remaining39    while i < len(left_arr):40        arr[k] = left_arr[i]41        i += 142        k += 14344    while j1 < len(right_arr[3, 43]):45        arr[k]→ 43 = right_arr[j]4346        j→ 2 += 147        k→ 4 += 1
    All 3 passes — pass 1 is the card above
    passright_arrright_arr[j]rightarr[k]jkarrleftmid
    1[3, 43]433431 → 23 → 4[27, 38, 3, 43, 9, 82, 10] → [3, 27, 38, 43, 9, 82, 10]01 → 3
    2[82]825820 → 15 → 6[3, 27, 38, 43, 9, 82, 10]44 → 5
    3[9, 10, 82]826822 → 36 → 7[3, 27, 38, 43, 9, 10, 82] → [3, 9, 10, 27, 38, 43, 82]03

  16. k ← 5

    35    j += 136k→ 5 += 1

  17. k ← 5

    35    j += 136k→ 5 += 1

  18. k ← 6

    35    j += 136k→ 6 += 1

  19. k ← 1

    35    j += 136k→ 1 += 1

  20. k ← 2

    35    j += 136k→ 2 += 1

  21. k ← 3

    35    j += 136k→ 3 += 1

  22. k ← 4

    35    j += 136k→ 4 += 1

  23. k ← 5

    35    j += 136k→ 5 += 1

  24. k ← 6

    35    j += 136k→ 6 += 1

  25. numbers ← [3, 9, 10, 27, 38, 43, 82]

    53print("Before:", numbers)54merge_sort_inplace(numbers→ [3, 9, 10, 27, 38, 43, 82])55print("After: ", numbers[3, 9, 10, 27, 38, 43, 82])
    outputAfter:  [3, 9, 10, 27, 38, 43, 82]

Characteristics

  • Time complexity: O(n log n) - always
  • Space complexity: O(n) - requires temporary lists
  • Stable: maintains relative order of equal elements
  • Not in-place: requires additional memory
  • Predictable: always same performance
guaranteed_performance O(n log n) in all cases - best, average, and worst

When to Use

  • Need guaranteed O(n log n) performance
  • Stability matters
  • Large datasets
  • External sorting

Exercise: practical.py

Implement merge sort to sort a list of log entries by timestamp, then merge two sorted log files into one