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]
مثالی ہے جب آپ کو 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 ہے جو آپ ہر جگہ دوبارہ استعمال کریں گے۔
تفصیلی جوابات کے ساتھ IT انٹرویو سوالات کی ایک لائبریری — جونیئر سے سینئر تک۔
عطیہ دیں