Merge Sort is a classic divide-and-conquer sorting algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves.
def merge(left, right):
result = []
i = j = 0
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
result.extend(left[i:])
result.extend(right[j:])
return result
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
Quick Sort is an efficient in-place sorting algorithm that uses partitioning to divide the array and recursively sort the partitions.
def partition(arr, low, high):
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort(arr, low, high):
if low < high:
pi = partition(arr, low, high)
quick_sort(arr, low, pi - 1)
quick_sort(arr, pi + 1, high)
Heap Sort uses a binary heap data structure to efficiently sort an array by repeatedly extracting the maximum element.
def heapify(arr, n, i):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
Algorithm | Time Complexity (Best) | Time Complexity (Average) | Time Complexity (Worst) | Space Complexity | Stability | Use Case |
---|---|---|---|---|---|---|
Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Stable | Linked lists, stable sorting |
Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) recursive stack | Not stable | General-purpose in-memory sort |
Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Not stable | Memory constrained environments |