Learn to implement and apply advanced sorting algorithms: Merge Sort and Quick Sort.
def merge_sort(arr):
# Base case: arrays with 0 or 1 element are already sorted
if len(arr) <= 1:
return arr
# Split array into two halves
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# Recursively sort both halves
return merge(merge_sort(left), merge_sort(right))
def merge(left, right):
result = []
left_index = 0
right_index = 0
# Compare elements from both arrays and merge them in sorted order
while left_index < len(left) and right_index < len(right):
if left[left_index] < right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
# Add remaining elements (if any)
result.extend(left[left_index:])
result.extend(right[right_index:])
return result
numbers = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(numbers)) # [3, 9, 10, 27, 38, 43, 82]
def quick_sort(arr, left=0, right=None):
if right is None:
right = len(arr) - 1
if left < right:
pivot_index = partition(arr, left, right)
quick_sort(arr, left, pivot_index - 1)
quick_sort(arr, pivot_index + 1, right)
return arr
def partition(arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i] # Swap elements
arr[i + 1], arr[right] = arr[right], arr[i + 1]
return i + 1 # Return pivot index
numbers = [10, 7, 8, 9, 1, 5]
print(quick_sort(numbers)) # [1, 5, 7, 8, 9, 10]
| Characteristic | Merge Sort | Quick Sort |
|---|---|---|
| Approach | Divide and conquer, merges sorted sublists | Divide and conquer, uses pivot to partition |
| Time Complexity | O(n log n) - consistent | Average: O(n log n), Worst: O(n²) |
| Space Complexity | O(n) - requires extra space | O(log n) - in-place partitioning |
| Stability | Stable (preserves order of equal elements) | Unstable (may change order of equal elements) |
| Best Use Cases | External sorting, linked lists, stability required | Internal sorting, arrays, memory constraints |
Test your understanding with these LeetCode problems: