In [1]:
def merge(A, p, q, r):
__debug__ and print(f"merge(A, {p}, {q}, {r}) -> L: A[{p}:{q+1}] R: A[{q+1}:{r+1}]")
# Create temporary arrays using Python list slicing
L = A[p : q + 1]
R = A[q + 1 : r + 1]
#__debug__ and print(f"L: {L} R: {R}")
# Initialize pointers for L, R, and the main array A
i = 0
j = 0
k = p
# Merge the temporary arrays back into A[p..r]
while i < len(L) and j < len(R):
__debug__ and print(f"L: {L} R: {R}")
if L[i] <= R[j]:
__debug__ and print(f"A[{k}] from L[{i}]: {L[i]}")
A[k] = L[i]
i += 1
else:
__debug__ and print(f"A[{k}] from R[{j}]: {R[j]}")
A[k] = R[j]
j += 1
k += 1
__debug__ and print(f"A: {A}")
# Copy any remaining elements of L
while i < len(L):
__debug__ and print(f"Remaining L: {L}")
__debug__ and print(f"A[{k}] from L[{i}]: {L[i]}")
A[k] = L[i]
i += 1
k += 1
# Copy any remaining elements of R
while j < len(R):
__debug__ and print(f"Remaining R: {L}")
__debug__ and print(f"A[{k}] from R[{j}]: {R[j]}")
A[k] = R[j]
j += 1
k += 1
def merge_sort(A, p, r, d):
d = d + 1
__debug__ and print(f"{'>> '*d} merge_sort(A, {p}, {r}, {d}) A[{p}:{r}]")
__debug__ and print(f"{' '*d} {A[p:r]} {A[r:]}")
# Base case: if p >= r, the array has 1 or 0 elements and is already sorted
if p < r:
# Find the midpoint to divide the array into two halves
# Use integer division (//) to get a whole number index
q = (p + r) // 2
# Recursively sort the first half
merge_sort(A, p, q, d)
# Recursively sort the second half
merge_sort(A, q + 1, r, d)
# Merge the two sorted halves
merge(A, p, q, r)
goto_level = d - 1
__debug__ and print(f"{'<< '*goto_level}")
# --- Test the Algorithm ---
if __name__ == "__main__":
# Sample unsorted array
test_array = [38, 27, 43, 3, 9, 82, 10]
print("Original array:", test_array, "\n")
# Call merge_sort.
# The starting index p is 0.
# The ending index r is the length of the array minus 1.
global d
d = 0
merge_sort(test_array, 0, len(test_array) - 1, d)
print("Sorted array: ", test_array)
Original array: [38, 27, 43, 3, 9, 82, 10]
>> merge_sort(A, 0, 6, 1) A[0:6]
[38, 27, 43, 3, 9, 82] [10]
>> >> merge_sort(A, 0, 3, 2) A[0:3]
[38, 27, 43] [3, 9, 82, 10]
>> >> >> merge_sort(A, 0, 1, 3) A[0:1]
[38] [27, 43, 3, 9, 82, 10]
>> >> >> >> merge_sort(A, 0, 0, 4) A[0:0]
[] [38, 27, 43, 3, 9, 82, 10]
<< << <<
>> >> >> >> merge_sort(A, 1, 1, 4) A[1:1]
[] [27, 43, 3, 9, 82, 10]
<< << <<
merge(A, 0, 0, 1) -> L: A[0:1] R: A[1:2]
L: [38] R: [27]
A[0] from R[0]: 27
A: [27, 27, 43, 3, 9, 82, 10]
Remaining L: [38]
A[1] from L[0]: 38
<< <<
>> >> >> merge_sort(A, 2, 3, 3) A[2:3]
[43] [3, 9, 82, 10]
>> >> >> >> merge_sort(A, 2, 2, 4) A[2:2]
[] [43, 3, 9, 82, 10]
<< << <<
>> >> >> >> merge_sort(A, 3, 3, 4) A[3:3]
[] [3, 9, 82, 10]
<< << <<
merge(A, 2, 2, 3) -> L: A[2:3] R: A[3:4]
L: [43] R: [3]
A[2] from R[0]: 3
A: [27, 38, 3, 3, 9, 82, 10]
Remaining L: [43]
A[3] from L[0]: 43
<< <<
merge(A, 0, 1, 3) -> L: A[0:2] R: A[2:4]
L: [27, 38] R: [3, 43]
A[0] from R[0]: 3
A: [3, 38, 3, 43, 9, 82, 10]
L: [27, 38] R: [3, 43]
A[1] from L[0]: 27
A: [3, 27, 3, 43, 9, 82, 10]
L: [27, 38] R: [3, 43]
A[2] from L[1]: 38
A: [3, 27, 38, 43, 9, 82, 10]
Remaining R: [27, 38]
A[3] from R[1]: 43
<<
>> >> merge_sort(A, 4, 6, 2) A[4:6]
[9, 82] [10]
>> >> >> merge_sort(A, 4, 5, 3) A[4:5]
[9] [82, 10]
>> >> >> >> merge_sort(A, 4, 4, 4) A[4:4]
[] [9, 82, 10]
<< << <<
>> >> >> >> merge_sort(A, 5, 5, 4) A[5:5]
[] [82, 10]
<< << <<
merge(A, 4, 4, 5) -> L: A[4:5] R: A[5:6]
L: [9] R: [82]
A[4] from L[0]: 9
A: [3, 27, 38, 43, 9, 82, 10]
Remaining R: [9]
A[5] from R[0]: 82
<< <<
>> >> >> merge_sort(A, 6, 6, 3) A[6:6]
[] [10]
<< <<
merge(A, 4, 5, 6) -> L: A[4:6] R: A[6:7]
L: [9, 82] R: [10]
A[4] from L[0]: 9
A: [3, 27, 38, 43, 9, 82, 10]
L: [9, 82] R: [10]
A[5] from R[0]: 10
A: [3, 27, 38, 43, 9, 10, 10]
Remaining L: [9, 82]
A[6] from L[1]: 82
<<
merge(A, 0, 3, 6) -> L: A[0:4] R: A[4:7]
L: [3, 27, 38, 43] R: [9, 10, 82]
A[0] from L[0]: 3
A: [3, 27, 38, 43, 9, 10, 82]
L: [3, 27, 38, 43] R: [9, 10, 82]
A[1] from R[0]: 9
A: [3, 9, 38, 43, 9, 10, 82]
L: [3, 27, 38, 43] R: [9, 10, 82]
A[2] from R[1]: 10
A: [3, 9, 10, 43, 9, 10, 82]
L: [3, 27, 38, 43] R: [9, 10, 82]
A[3] from L[1]: 27
A: [3, 9, 10, 27, 9, 10, 82]
L: [3, 27, 38, 43] R: [9, 10, 82]
A[4] from L[2]: 38
A: [3, 9, 10, 27, 38, 10, 82]
L: [3, 27, 38, 43] R: [9, 10, 82]
A[5] from L[3]: 43
A: [3, 9, 10, 27, 38, 43, 82]
Remaining R: [3, 27, 38, 43]
A[6] from R[2]: 82
Sorted array: [3, 9, 10, 27, 38, 43, 82]