Divide & Conquer Sorting
Merge Sort Algorithm
Merge Sort is an efficient, comparison-based sorting algorithm that uses a divide-and-conquer strategy to sort arrays in guaranteed $O(N \log N)$ time across all cases.
Best CaseO(N log N)
Average CaseO(N log N)
Worst CaseO(N log N)
Space ComplexityO(N)
Python Implementation
Run & Visualizedef merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left_half = merge_sort(arr[:mid])
right_half = merge_sort(arr[mid:])
return merge(left_half, right_half)
def merge(left, right):
sorted_arr = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
sorted_arr.append(left[i])
i += 1
else:
sorted_arr.append(right[j])
j += 1
sorted_arr.extend(left[i:])
sorted_arr.extend(right[j:])
return sorted_arr
data = [38, 27, 43, 3, 9, 82, 10]
result = merge_sort(data)
print(f"Sorted array: {result}")