Merge sort ایک divide-and-conquer، stable sort ہے جو guaranteed O(n log n) وقت میں چلتا ہے۔ یہ array کو آدھا کرتا ہے، ہر آدھے کو recursively sort کرتا ہے، پھر دونوں sorted نصفوں کو merge کرتا ہے۔
یہ خیال
ایک single element پہلے سے sorted ہے (base case)۔ دو sorted lists کو merge کرنا linear ہے، اور ہم log n levels میں merge کرتے ہیں۔
مثال
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
return merge(left, right)
def merge(a, b):
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: # <= keeps it stable
result.append(a[i]); i += 1
else:
result.append(b[j]); j += 1
result.extend(a[i:]); result.extend(b[j:])
return result
merge_sort([5, 2, 4, 1, 3]) # -> [1, 2, 3, 4, 5]
Complexity
- Time: O(n log n) تمام حالتوں میں (best, average, worst)۔
- Space: O(n) merge buffers کے لیے (in-place نہیں)۔
کب استعمال کریں / خطرے
مثالی ہے جب آپ کو stability یا guaranteed O(n log n) کی ضرورت ہو، اور linked lists اور بہت بڑی files کی external sorting کے لیے۔ اضافی O(n) memory اس کی main drawback ہے۔
یہ کیوں اہم ہے
Merge sort input سے قطع نظر O(n log n) کی guarantee دیتا ہے، quicksort کے O(n²) worst case کے برعکس۔
اس کی stability برابر keys کی relative order کو محفوظ رکھتی ہے، جو multi-key sorting کے لیے اہم ہے۔
Merge step ایک reusable primitive ہے، اور divide-and-conquer structure ایک template ہے جو آپ ہر جگہ دوبارہ استعمال کریں گے۔