Merge sort એ divide-and-conquer, stable સોર્ટ છે જે ગ્યારંટીવાળા O(n log n) સમયમાં ચાલે છે. તે એરેને અડધાથી વહેંચે છે, દરેક અર્ધને પુનરાવર્તિતપણે સોર્ટ કરે છે, પછી બે સોર્ટેડ અર્ધોને મર્જ કરે છે.
એક જ તત્વ પહેલાથી સોર્ટેડ છે (આધાર કેસ). બે સોર્ટેડ યાદીઓને મર્જ કરવું રેખીય છે, અને આપણે લોગ 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]
જ્યારે તમને stability અથવા ગ્યારંટીવાળા O(n log n)ની જરૂર હોય ત્યારે આદર્શ, અને linked lists અને વિશાળ ફાઈલોના external sorting માટે. વધારાનું O(n) મેમરી તેની મુખ્ય ખામી છે.
Merge sort ઇનપુટ પર ધ્યાન આપતા O(n log n) ગ્યારંટી આપે છે, quicksort ના O(n²) સૌથી ખરાબ કેસ તરફથી વિપરીત.
તેની stability સમાન કીઓનો સંબંધિત ક્રમ સંરક્ષિત કરે છે, જે બહુ-કી સોર્ટિંગ માટે મહત્વપૂર્ણ છે.
મર્જ પગલું એક પુનઃઉપયોગી આદિમ છે, અને divide-and-conquer માળખું એક template છે જે તમે સર્વત્ર પુનઃઉપયોગ કરશો.