Merge sort ఒక విభజన-మరియు-జయించు, స్థిరమైన క్రమబద్ధీకరణ, ఇది గ్యారంటీ ఇచ్చిన O(n log n) సమయంలో నడుస్తుంది. ఇది శ్రేణిని సగానికి విభజిస్తుంది, ప్రతి సగం పునరావృతమైన క్రమబద్ధీకరిస్తుంది, తరువాత రెండు క్రమబద్ధీకరించిన సగాలను విలీనం చేస్తుంది.
ఒక ఏకైక మూలకం ఇప్పటికే క్రమబద్ధీకరించబడింది (ఆధార సందర్భం). రెండు క్రమబద్ధీకరించిన జాబితాలను విలీనం చేయడం రేఖీయ, మరియు మేము log n స్థాయిల విలీనం చేస్తాము.
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]
స్థిరత్వం లేదా గ్యారంటీ ఇచ్చిన O(n log n) అవసరమైనప్పుడు, మరియు లింక్ చేసిన జాబితాలు మరియు బాహ్య క్రమబద్ధీకరణ భారీ ఫైల్ల కోసం సరిపోతుంది. అতిరేక O(n) మెమరీ దాని ప్రధాన లోపం.
Merge sort ఇన్పుట్ పర్వాలేకుండా O(n log n)కు భరోసా ఇస్తుంది, quicksort యొక్క O(n²) గరీష్ట సందర్భానికి భిన్నంగా.
ఇది సమాన కీల సాపేక్ష క్రమాన్ని సంరక్షిస్తుంది, ఇది బహుళ-కీ క్రమబద్ధీకరణకు ముఖ్యమైనది.
విలీనం దశ పునర్వినియోగ చేయగల ఆదిమ, మరియు విభజన-మరియు-జయించు నిర్మాణం మీరు సర్వత్రా పునరుపయోగించే టెంప్లేట్.