# Merge sort implementation in Python.
# The algorithm works by:
# 1. Recursively splitting the list into two halves.
# 2. Sorting each half.
# 3. Merging the two sorted halves into one sorted list.
#
# This approach guarantees O(n log n) time complexity and stable sorting.
def merge(left, right):
"""
Merge two sorted lists into one sorted list.
The function walks through both lists and picks the smallest
available element each time.
"""
merged = []
i = j = 0
# Compare elements from both lists and append the smaller one
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i])
i += 1
else:
merged.append(right[j])
j += 1
# Append any remaining elements
merged.extend(left[i:])
merged.extend(right[j:])
return merged
def merge_sort(arr):
"""
Recursively sort a list using merge sort.
If the list has length 0 or 1, it is already sorted.
Otherwise, split it, sort each half, and merge.
"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_sorted = merge_sort(arr[:mid])
right_sorted = merge_sort(arr[mid:])
return merge(left_sorted, right_sorted)
if __name__ == "__main__":
data = [38, 27, 43, 3, 9, 82, 10]
result = merge_sort(data)
print("Original:", data)
print("Sorted:", result)
"""
run:
Original: [38, 27, 43, 3, 9, 82, 10]
Sorted: [3, 9, 10, 27, 38, 43, 82]
"""
