42 lines
955 B
Python
42 lines
955 B
Python
def merge_sort(arr):
|
|
# If the array length is less than 2, no sorting is needed
|
|
if len(arr) <= 1:
|
|
return arr
|
|
|
|
# Find the middle of the array
|
|
mid = len(arr) // 2
|
|
|
|
# Divide the array into two halves
|
|
left_half = merge_sort(arr[:mid])
|
|
right_half = merge_sort(arr[mid:])
|
|
|
|
# Merge two sorted halves
|
|
return merge(left_half, right_half)
|
|
|
|
|
|
def merge(left, right):
|
|
result = []
|
|
i = j = 0
|
|
|
|
# As long as there are elements left in both lists
|
|
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 the remaining elements (one of the lists may run out early)
|
|
result.extend(left[i:])
|
|
result.extend(right[j:])
|
|
return result
|
|
|
|
|
|
# Example:
|
|
|
|
nums = [5, 2, 4, 6, 1, 3]
|
|
print("Before sorting:", nums)
|
|
|
|
nums = merge_sort(nums)
|
|
print("After sorting:", nums) |