Το Merge sort είναι ένας ταξινόμηση divide-and-conquer, σταθερή που τρέχει σε εγγυημένο 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) ανεξάρτητα από την είσοδο, σε αντίθεση με τη χειρότερη περίπτωση O(n²) του quicksort.
Η σταθερότητά του διατηρεί τη σχετική σειρά ίσων κλειδιών, γεγονός που είναι σημαντικό για ταξινόμηση πολλαπλών κλειδιών.
Το βήμα συγχώνευσης είναι μια επανεπιχρησιμοποιήσιμη πρωτόγονη λειτουργία, και η δομή divide-and-conquer είναι ένα πρότυπο που θα επανεχρησιμοποιήσετε παντού.