Merge sort ਇੱਕ divide-and-conquer, stable sort ਹੈ ਜੋ ਗ੍ਰਹਣਯੋਗ O(n log n) ਸਮੇਂ ਵਿੱਚ ਚਲਦਾ ਹੈ। ਇਹ array ਨੂੰ ਅੱਧੀ ਵਿੱਚ ਵਿਭਾਜਿਤ ਕਰਦਾ ਹੈ, ਹਰੇਕ ਅੱਧੇ ਨੂੰ recursively sort ਕਰਦਾ ਹੈ, ਫਿਰ ਦੋ sorted ਅੱਧਿਆਂ ਨੂੰ merge ਕਰਦਾ ਹੈ।
ਇੱਕ ਸਿੰਗਲ element ਪਹਿਲਾਂ ਹੀ sorted ਹੈ (base case)। ਦੋ sorted lists ਨੂੰ merge ਕਰਨਾ linear ਹੈ, ਅਤੇ ਅਸੀਂ log n ਪੱਧਰਾਂ ਦਾ merging ਕਰਦੇ ਹਾਂ।
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 ਜਾਂ ਗ੍ਰਹਣਯੋਗ O(n log n) ਚਾਹੀਦਾ ਹੈ, ਅਤੇ linked lists ਅਤੇ external sorting ਵੱਡੀਆਂ ਫਾਈਲਾਂ ਲਈ। ਵਾਧੂ O(n) ਮੈਮੋਰੀ ਇਸਦੀ ਮੁੱਖ ਕਮਜ਼ੋਰੀ ਹੈ।
Merge sort input ਦੀ ਪਰਵਾਹ ਕੀਤੇ ਬਿਨਾਂ O(n log n) ਦੀ ਗ੍ਰਹਣਯੋਗਤਾ ਦਿੰਦਾ ਹੈ, quicksort ਦੇ O(n²) worst case ਦੀ ਬਜਾਇ।
ਇਸਦੀ stability ਬਰਾਬਰ keys ਦਾ ਸਾਪੇਖ ਕ੍ਰਮ ਸੁਰੱਖਿਤ ਰੱਖਦੀ ਹੈ, ਜੋ multi-key sorting ਲਈ ਮਾਇਨੇ ਰੱਖਦਾ ਹੈ।
Merge step ਇੱਕ reusable primitive ਹੈ, ਅਤੇ divide-and-conquer structure ਇੱਕ template ਹੈ ਜੋ ਤੁਸੀਂ ਸਰਵਤ੍ਰ ਦੁਬਾਰਾ ਵਰਤੋਂਗੇ।