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²) மோசம் நிலைக்கு மாறாக.
இதன் நிலைத்தன்மை சம விசைகளின் ஒப்பீட்டு வரிசையைப் பாதுகாக்கிறது, இது பல-விசை வரிசைப்படுத்தலுக்கு முக்கியம்.
இணைப்பு படி மீண்டும் பயன்படுத்தக்கூடிய ஆதிமை ஆகும், மற்றும் பிభாग-மற்றும்-வெற்றி கட்டமைப்பு நீங்கள் எங்கும் மீண்டும் பயன்படுத்தும் வார்ப்பளவு ஆகும்.