Merge Sort (Python)

[qingquan-li]

# Function to merge two sorted sub-arrays
def merge(arr: list[int], p: int, q: int, r: int):
    left: list[int] = arr[p:q+1]  # arr[p..q]
    right: list[int] = arr[q+1:r+1]  # arr[q+1..r]

    i: int = 0  # Pointer (index) for left sub-array
    j: int = 0  # Pointer for right sub-array
    k: int = p  # Pointer for the original array
    # k is the index that tracks the position in the original array (arr)
    # where the next element from the sorted sub-arrays should be placed.
    # The "original array (arr)" refers to the full array, but during the
    # recursive steps of merge sort, we treat portions of it as sub-arrays
    # using the indices p, q, and r.
    # We should not set k = 0 because that would incorrectly place the merged
    # elements at the start of the array, overwriting previous sections and
    # breaking the sort.

    # Merge the two sub-arrays back into arr[p..r]
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            arr[k] = left[i]
            i += 1
        else:
            arr[k] = right[j]
            j += 1
        k += 1

    # Copy any remaining elements of left[] if any
    while i < len(left):
        arr[k] = left[i]
        i += 1
        k += 1

    # Copy any remaining elements of right[] if any
    while j < len(right):
        arr[k] = right[j]
        j += 1
        k += 1


# Recursive merge_sort function
def merge_sort(arr: list[int], p: int, r: int) -> None:
    if p < r:
        q: int = (p + r) // 2  # Find the midpoint, taking the floor value
        merge_sort(arr, p, q)  # Sort the first half
        merge_sort(arr, q + 1, r)  # Sort the second half
        merge(arr, p, q, r)  # Merge the sorted halves


arr: list[int] = [2, 1, 6, 3, 4]
merge_sort(arr, 0, len(arr) - 1)
print(arr)  # [1, 2, 3, 4, 6]

Visualize:

• https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/visualize/