αγγλικά : Merge sort
γαλλικά : Tri fusion
γερμανικά : Mergesort
Στην πληροφορική, η ταξινόμηση με συγχώνευση (αγγλ.: Merge sort) είναι ένας αλγόριθμος ταξινόμησης χρονικής πολυπλοκότητας O (n log n) βασισμένος στη σύγκριση. Στις περισσότερες υλοποιήσεις του, παράγεται μία ευσταθής ταξινόμηση, που σημαίνει ότι η υλοποίηση διατηρεί τη σειρά των ίσων στοιχείων από την είσοδο, στην ταξινομημένη έξοδο. Η ταξινόμηση με συγχώνευση είναι αλγόριθμος Διαίρει και Βασίλευε που εφευρέθηκε από τον Τζων φον Νώυμαν το 1945[1]. Η λεπτομερής περιγραφή και ανάλυση του αλγορίθμου εμφανίστηκε σε μια αναφορά των Herman Goldstine και Νώυμαν ήδη από το 1948[2].
Επισκόπηση
Εννοιολογικά, η ταξινόμηση με συγχώνευση λειτουργεί ως εξής:
Διαιρείται η μη ταξινομημένη λίστα σε n υπολίστες, με την καθεμιά να περιέχει από 1 στοιχείο (η λίστα του ενός στοιχείου θεωρείται ταξινομημένη).
Επαναληπτικά, συγχωνεύονται οι υπολίστες, ώστε να παραχθούν νέες υπολίστες, μέχρι να απομείνει 1 μόνον υπολίστα (η οποία θα είναι ταξινομημένη.)
Yλοποίηση από πάνω προς τα κάτω
Παράδειγμα σε ψευδοκώδικα για την από πάνω προς τα κάτω του αλγορίθμου ταξινόμησης με συγχώνευση, το οποίο χρησιμοποιεί αναδρομή ώστε να διαιρέσει την λίστα σε υπολίστες, κατόπιν συγχωνεύει τις υπολίστες όσο οι επιστροφές ανεβάζουν το πρόγραμμα στην αλληλουχία των κλήσεων.
συνάρτηση merge_sort(λίστα μ)
// αν το μέγεθος της λίστας είναι 1, θεώρησέ την ταξινομημένη και επίστρεψέ την
αν μήκος(μ) <= 1
επίστρεψε μ
// αλλιώς το μήκος της λίστας είναι > 1, επομένως χώρισε τη λίστα σε δύο υπολίστες
μεταβλητή λίστα αριστερά, δεξιά
μεταβλητή ακέραιος μέσον = μήκος(μ) / 2
για κάθε x στο μ μέχρι το μέσον
πρόσθεσε το x στο αριστερά
για κάθε x στο μ μετά ή ακριβώς στο μέσον
πρόσθεσε το x στα δεξιά
// κάλεσε αναδρομικά την merge_sort() ώστε να χωρίσεις περαιτέρω κάθε υπολίστα
// μέχρι το μέγεθος της υπολίστας να μείνει 1
αριστερά = merge_sort(αριστερά)
δεξιά = merge_sort(δεξιά)
// συγχώνευσε τις υπολίστες που επιστράφηκαν από τις προηγούμενες κλήσεις στην merge_sort()
// και επίστρεψε την προκύπτουσα συγχωνευμένη υπολίστα
επέστρεψε merge(αριστερά, δεξιά)
Στο παρόν παράδειγμα, η συνάρτηση merge συγχωνεύει την αριστερή και τη δεξιά υπολίστα.
συνάρτηση merge(αριστερά, δεξιά)
μεταβλητή λίστα αποτέλεσμα
όσο μήκος(αριστερά) > 0 ή μήκος(δεξιά) > 0
αν μήκος(αριστερά) > 0 και μήκος(δεξιά) > 0
αν πρώτο(αρστερά) <= πρώτο(δεξιά)
προσάρτησε πρώτο(αριστερά) στο αποτέλεσμα
αριστερά = υπόλοιπα(αριστερά)
αλλιώς
προσάρτησε πρώτο(δεξιά) στο αποτέλεσμα
δεξιά = υπόλοιπα(δεξιά)
αλλιώς αν μήκος(αριστερά) > 0
προσάρτησε πρώτο(αριστερά) στο αποτέλεσμα
αριστερά = υπόλοιπα(αριστερά)
αλλιώς αν μήκος(δεξιά) > 0
προσάρτησε πρώτο(δεξιά) στο αποτέλεσμα
δεξιά = υπόλοιπα(δεξιά)
τέλος του όσο
επέστρεψε αποτέλεσμα
Υλοποίηση από κάτω προς τα πάνω
Παράδειγμα ψευδοκώδικα για την από κάτω προς τα πάνω του αλγορίθμου ταξινόμησης με συγχώνευση, το οποίο μεταχειρίζεται τη λίστα σαν έναν πίνακα από n υπολίστες (εδώ αποκαλούνται αλληλουχίες(runs)) μεγέθους 1, και επαναληπτικά συγχωνεύει τις υπολίστες μπρος και πίσω μεταξύ δύο προσωρινών χώρων:
/* ο πίνακας A[] έχει τα στοιχεία προς ταξινόμηση - ο πίνακας B[] είναι ο πίνακας εργασίας */
BottomUpSort(int n, array A[n], array B[n])
{
int width;
/* each 1-element run in A is already "sorted". */
/* Δημιούργησε αλλεπάλληλες μακρύτερες αλληλουχίες μήκους 2, 4, 8, 16... μέχρι να ταξινομηθεί όλος ο πίνακας */
for (width = 1; width < n; width = 2 * width)
{
int i;
/* ο πίνακας A είναι γεμάτος από αλληλουχίες μήκους width */
for (i = 0; i < n; i = i + 2 * width)
{
/* Συγχώνευσε δυο αλληλουχίες: την A[i:i+width-1] και την A[i+width:i+2*width-1] στο B[] */
/* ή αντίγραψε την A[i:n-1] στο B[] ( αν(i+width >= n) ) */
BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B);
}
/* Τώρα ο πίνακας εργασίας B είναι γεμάτος με αλληλουχίες μήκους 2*width */
/* αντέγραψε τον πίνακα B στον πίνακα A για την επόμενη επανάληψη */
/* μια πιο αποδοτική υλοποίηση θα αντιμετέθετε τους ρόλους του A και του B */
CopyArray(A, B, n);
/* τώρα ο πίνακας A είναι γεμάτος με αλληλουχίες μήκους 2*width */
}
}
BottomUpMerge(array A[], int iLeft, int iRight, int iEnd, array B[])
{
int i0 = iLeft;
int i1 = iRight;
int j;
/* όσο υπάρχουν στοιχεία στην αριστερή ή στη δεξιά λίστα */
for (j = iLeft; j < iEnd; j++)
{
/* αν η αριστερή λίστα έχει κεφαλή και είναι <= από υπάρχουσα κεφαλή της δεξιάς λίστας */
if (i0 < iRight && (i1 >= iEnd || A[i0] <= A[i1]))
{
B[j] = A[i0];
i0 = i0 + 1;
}
else
{
B[j] = A[i1];
i1 = i1 + 1;
}
}
}
Υβριδική ταξινόμηση με συγχώνευση
Στην υβριδική ταξινόμηση, χρησιμοποιείται κάποιος άλλος αλγόριθμος για να ταξινομηθούν οι σχετικά μικρές υπολίστες:
Διαίρεσε τη μη ταξινομημένη λίστα σε έναν αριθμό σχετικά μικρών υπολιστών και ταξινόμησέ τες χρησιμοποιώντας κάποιον αλγόριθμο ταξινόμησης.
Επαναληπτικά συγχώνευσε τις υπολίστες ώστε να παραχθούν νέες υπολίστες μέχρι να απομείνει μόνο 1 υπολίστα (η ταξινομημένη λίστα)
Ταξινόμηση με φυσική συγχώνευση
Η ταξινόμηση με φυσική συγχώνευση (Natural merge sort) είναι παρόμοια με την από κάτω προς τα πάνω ταξινόμηση συγχώνευσης, με τη διαφορά ότι κάθε φυσικά προκύπτουσα αλληλουχία (ήδη ταξινομημένη ακολουθία) στην είσοδο αξιοποιείται. Στην προσέγγιση από κάτω προς τα πάνω, το σημείο εκκίνησης προϋποθέτει ότι η κάθε αλληλουχία έχει μήκος ενός στοιχείου. Στην πράξη, η τυχαία είσοδος έχει πολλές μικρές αλληλουχίες που τυχαίνει να είναι ήδη ταξινομημένες. Σε μια τυπική περίπτωση, η ταξινόμηση με φυσική συγχώνευση μπορεί να μη χρειαστεί τόσες πολλές επαναλήψεις επειδή υπάρχουν λιγότερες αλληλουχίες να συγχωνευτούν. Για παράδειγμα, στην καλύτερη περίπτωση, η είσοδος είναι ήδη ταξινομημένη (δηλ. είναι μία αλληλουχία), οπότε η ταξινόμηση με φυσική συγχώνευση θα κάνει μόνο μια επανάληψη στα δεδομένα.
Ανάλυση
Αλγόριθμος ταξινόμησης με συγχώνευση που χρησιμοποιείται για την ταξινόμηση ενός πίνακα με 7 ακέραιους αριθμούς. Αυτά είναι τα βήματα που θα εκτελούσε ένας άνθρωπος για να προσομοιώσει την ταξινόμηση με συγχώνευση (προσέγγιση από πάνω προς τα κάτω).
Στην ταξινόμηση n στοιχείων, η ταξινόμηση με συγχώνευση έχει μέση και χειρότερη επίδοση ίση με O(n log n). Εάν ο χρόνος εκτέλεσης της ταξινόμησησς με συγχώνευση για μια λίστα μήκους n είναι T(n), τότε η επανάληψη T(n) = 2T(n/2) + n προκύπτει από τον ορισμό του αλγορίθμου (εφαρμογή του αλγορίθμου σε δύο λίστες μισού μεγέθους σε σχέση με την αρχική, και προσθήκη των n βημάτων που χρειάζονται για να συγχωνευτούν οι δύο λίστες). Η κλειστή μορφή προκύπτει από το «master theorem».
Στην χειρότερη περίπτωση, ο αριθμός των συγκρίσεων που κάνει η ταξινόμηση με συγχώνευση είναι ίσος ή ελαφρά μικρότερος από (n ⌈lg n⌉ - 2⌈lg n⌉ + 1), τιμή που βρίσκεται μεταξύ του (n lg n - n + 1) και του (n lg n + n + O(lg n)).[3]
Για μεγάλα n και λίστα εισόδου τυχαία ταξινομημένη, ο αναμενόμενος (μέσος) αριθμός συγκρίσεων προσεγγίζει το α·n, όντας μικρότερος από ό,τι στην χειρότερη περίπτωση όπου α = − 1 + ∑ k = 0 ∞ 1 2 k + 1 ≈ 0.2645. {\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.} {\displaystyle \alpha =-1+\sum _{k=0}^{\infty }{\frac {1}{2^{k}+1}}\approx 0.2645.}
Στην χειρότερη περίπτωση, η ταξινόμηση με συγχώνευση εκτελεί περίπου 39% λιγότερες συγκρίσεις από όσες η quicksort εκτελεί στη μέση περίπτωση- η ταξινόμηση με συγχώνευση πάντοτε κάνει λιγότερες συγκρίσεις από την quicksort, εκτός από εξαιρετικά σπάνιες περιπτώσεις, όπου η χειρότερη περίπτωση της ταξινόμησης με συγχώνευση ισοδυναμεί με την καλύτερη περίπτωση της quicksort. Όσον αφορά τις μετακινήσεις, η χειρότερη πολυπλοκότητα της ταξινόμησης με συγχώνευση είναι O(n log n)— η ίδια με την καλύτερη της quicksort, ενώ η καλύτερη περίπτωση της ταξινόμησης με συγχώνευση κάνει περίπου τις μισές επαναλήψεις σε σχέση με την χειρότερη περίπτωση.[εκκρεμεί παραπομπή]
Οι αναδρομικές υλοποιήσεις της ταξινόμησης με συγχώνευση εκτελούν 2n − 1 κλήσεις μεθόδων στην χειρότερη περίπτωση, σε σύγκριση με τις n της quicksort, οπότε η ταξινόμηση με συγχώνευση έχει σχεδόν διπλάσιο φόρτο αναδρομής από την quicksort. Ωστόσο, οι επαναληπτικές, μη αναδρομικές, υλοποιήσεις της ταξινόμησης με συγχώνευση, οι οποίες αποφεύγουν τον φόρτο των κλήσεων μεθόδων. δεν είναι δύσκολο να γραφούν. Η πιο συνήθης υλοποίηση της ταξινόμησης με συγχώνευση δεν ταξινομεί επί τόπου, επομένως, μνήμη με μέγεθος όσο αυτό της εισόδου πρέπει να δεσμευτεί και για την αποθήκευση της ταξινομημένης εξόδου (δείτε παρακάτω για εκδόσεις που χρειάζονται μόνο n/2 επιπλέον χώρου).
Η επί τόπου ευσταθής ταξινόμηση είναι δυνατή αλλά πιο πολύπλοκη, και συνήθως λίγο πιο αργή, ακόμα και αν ο αλγόριθμος τρέχει σε χρόνο (n log n) (Katajainen, Pasanen & Teuhola 1996). Μια μέθοδος επί τόπου ταξινόμησης με συγχώνευση είναι να συγχωνεύονται τα τμήματα αναδρομικά.[4] Όπως και στην απλή ταξινόμηση με συγχώνευση, η επί τόπου συγχώνευση με ταξινόμηση είναι επίσης ευσταθής ταξινόμηση. Η ευσταθής ταξινόμηση συνδεδεμένων λιστών είναι απλούστερη. Σε αυτήν την περίπτωση, ο αλγόριθμος δεν χρησιμοποιεί επιπλέον χώρο εκτός από αυτόν που είναι ήδη δεσμευμένος για την αναπαράσταση της λίστας, πέρα από τα O(log(k)) που χρησιμοποιούνται για το ίχνος της αναδρομής.
Η ταξινόμηση με συγχώνευση είναι πιο αποδοτική από την quick sort για κάποοιυς τύπους λιστών, εάν τα δεδομένα που πρόκειται να συγχωνευθούν μπορούν να προσπελαστούν μόνο σειριακά, και για αυτό είναι δημοφιλής σε γλώσσες όπως η Lisp, όπου οι σειραϊκά προσπελάσιμες δομές δεδομένων είναι πολύ κοινές. Αντίθετα από κάποιες (αποδοτικές) υλοποιήσεις της quicksort, η ταξινόμηση με συγχώνευση είναι ευσταθής εφόσον η συγχώνευση υλοποιηθεί σωστά.
Η ταξινόμηση με συγχώνευση έχει και κάποια μειονεκτήματα. Ένα από αυτά είναι η χρήση 2n θέσεων μνήμης; οι επιπλέον n θέσεις συνήθως χρησιμοποιούνται επειδή η επί τόπου συγχώνευση δύο ταξινομημένων συνόλων είναι πιο περίπλοκη και θα χρειαζόταν περισσότερες συγκρίσεις και μετακινήσεις. Όμως, παρά την χρησιμοποίηση αυτού του χώρου, ο αλγόριθμος εκτελεί πολλές εργασίες: Τα περιεχόμενα του m αντιγράφονται πρώτα στους πίνακες αριστερά και δεξιά και αργότερα στη λίστα αποτέλεσμα με κάθε κλήση της merge_sort (τα ονόματα των μεταβλητών αντιστοιχούν στον ψευδοκώδικα παραπάνω). Μια εναλλακτική περίπτωση για την αντιγραφή είναι να αντιστοιχιστεί έναν νέο πεδίο για κάθε στοιχείο στο m. Αυτό το πεδίο θα χρησιμοποιείται για να συνδέει τα στοιχεία και οποιεσδήποτε άλλες πληροφορίες σε μια ταξινομημένη λίστα (το στοιχείο μαζί με τις σχετικές πληροφορίες ονομάζεται εγγραφή). Κατόπιν, η συγχώνευση των ταξινομημένων λιστών προχωράει με την αλλαγή της τιμής του συνδέσμου αυτού - δεν χρειάζεται να μετακινηθεί καμία εγγραφή. Ένα πεδίο που περιέχει μόνο το σύνδεσμο θα είναι σε γενικές γραμμές μικρότερο από μια ολόκληρη εγγραφή οπότε θα χρειαστεί και λιγότερος χώρος.
Μια άλλη εναλλακτική για την μείωση του επιπλέον χώρου σε n/2 είναι να διατηρηθούν οι πίνακες αριστερά και δεξιά σα μια συνδυασμένη δομή, να αντιγράφεται μόνο το αριστερό τμήμα του m σε έναν προσωρινό χώρο, και να κατευθύνεται η ρουτίνα merge ώστε να τοποθετεί τη συγχωνευμένη έξοδο στο m. Σε αυτήν την έκδοση είναι προτιμότερο να δεσμεύεται ο προσωρινός χώρος εκτός της ρουτίνας merge, ώστε μόνο μια δέσμευση να είναι απαραίτητη. Η επιπλέον αντιγραφή που αναφέρεται στην προηγούμενη παράγραφο αντιμετωπίζεται επίσης, αφού το τελευταίο ζευγάρι γραμμών πριν από τη δήλωση επέστρεψε αποτέλεσμα (συνάρτηση merge στον ψευδοκώδικα παραπάνω) γίνεται περιττό.
Η ταξινόμηση με συγχώνευση μπορεί να γίνει επίσης συγχωνεύονται περισσότερες από δύο υπολίστες κάθε φορά, χρησιμοποιώντας έναν αλγόριθμο συγχώνευσης ν - δρόμων. Ωστόσο, ο αριθμός των λειτουργιών είναι προσεγγιστικά ο ίδιος. Ας υποθέσουμε ότι συγχωνεύουμε k υπολίστες μονομιάς, όπου χάριν απλότητας το k είναι δύναμη του 2. Τότε η αναδρομική σχέση γίνεται T(n) = k T(n/k) + O(n log k). (Το τελευταίο τμήμα προέρχεται από τον αλγόριθμο συγχώνευσης, οποίος όταν υλοποιείται με τον ιδανικό τρόπο, χρησιμοποιώντας έναν σωρό ή έναν αυτο-ισορροπούμενο δυαδικό δέντρο αναζήτησης, παίρνει O (log k) χρόνο ανά στοιχείο.) Εάν πάρουμε την αναδρομική σχέση για την κλασσική ταξινόμηση με συγχώνευση (T(n) = 2T(n/2) + O(n)) και την αναπτύξουμε log2k φορές, παίρνουμε την ίδια αναδρομική σχέση. Αυτό ισχύει ακόμα και αν το k δεν είναι σταθερά.
Χρήση με οδηγούς ταινίας
Οι αλγόριθμοι ταξινόμησης με συγχώνευση επέτρεψαν την ταξινόμηση μεγάλων συνόλων δεδομένων σε πρώιμους υπολογιστές που είχαν μικρή μνήμη τυχαίας προσπέλασης (RAM) σε σχέση με τα μοντέρνα καθιερωμένα μεγέθη. Οι εγγραφές αποθηκεύονταν σε μαγνητική ταινία και επεξεργάζονταν σε συσκευές μαγνητικών ταινιών όπως αυτές IBM 729.
Η εξωτερική ταξινόμηση με συγχώνευση έχει πρακτική σημασία όταν οδηγοί δίσκων ή ταινίας και τα δεδομένα προς αποθήκευση είναι πολύ μεγάλα για να χωρέσουν στην ταινία ή το δίσκο. Η εξωτερική ταξινόμηση είναι ο τρόπος με τον οποίο η ταξινόμηση με συγχώνευση υλοποιείται με οδηγούς δίσκων. Μία τυπική ταξινόμηση με οδηγό ταινίας χρησιμοποιεί τέσσερεις οδηγούς ταινίας. Όλες οι λειτουργίες εισόδου/εξόδου είναι σειριακές (εκτός από τις επανελίξεις της ταινίας προς τα πίσω στο τέλος κάθε περάσματος). Μια ελάχιστη υλοποίηση μπορεί να γίνει με μόνο 2 προσωρινές αποθήκες εγγραφών και μερικές μεταβλητές.
Έστω ότι ονομάζουμε τους τέσσερεις οδηγούς ταινίας Α, Β, Γ, Δ, με τα αρχικά δεδομένα στο Α και χρησιμοποιώντας μόνο 2 προσωρινές αποθήκες εγγραφών, ο αλγόριθμος τότε είναι παρόμοιος με την Naming the four tape drives as A, B, C, D, with the original data on A, and using only 2 record buffers, the algorithm is similar to #Υλοποίηση_από_κάτω_προς_τα_πάνω, χρησιμοποιώντας ζευγάρια οδηγών τανιίας αντί για πίνακες στη μνήμη. Αυτός ο βασικός αλγόριθμος μπορεί να περιγραφεί ως εξής:
Συγχώνευσε τα ζευγάρια του Α - γράφοντας υπολίστες δύο εγγραφών εναλλάξ στο Γ και το Δ.
Συγχώνευσε τις υπολίστες δύο εγγραφών από το Φ και το Δ σε υπολίστες τεσσάρων εγγραφών - γράφοντάς τες εναλλάξ στο Α και το Β.
Συγχώνευσε στις υπολίστες των τεσσάρων εγγραφών από το Α και το Β σε άλλες των 8 εγγραφών - γράφοντάς τες εναλλάξ στο Γ και το Δ.
Επανάλαβε έως ότου έχει μείνει μια λίστα που περιέχει όλα τα δεδομένα, ταξινομημένα --- με log2(n) περάσματα.
Αντί να ξεκινήσει με πολύ μικρές αλληλουχίες, το αρχικό πέρασμα θα διαβάσει πολλές εγγραφές στη μνήμη, θα κάνει μια εσωτερική ταξινόμηση ώστε να δημιουργηθεί μια μεγάλη αλληλουχία, και κατόπιν κατανέμει αυτές τις μεγάλες αλληλουχίες στο σύνολο εξόδου. Το βήμα αυτό βοηθά στο να αποφευχθούν πολλά πρώιμα περάσματα. Για παράδειγμα, μια εσωτερική ταξινόμηση 1024 εγγραφών θα γλιτώσει 9 περάσματα. Η εσωτερική ταξινόμηση είναι συνήθως μεγάλη, επειδή έχει αυτό το πλεονέκτημα. Στην πραγματικότητα, υπάρχουν τεχνικές με τις οποίες οι αρχικές αλληλουχίες μπορούν να γίνουν μεγαλύτερες από τη διαθέσιμη εσωτερική μνήμη.[5]
Μια πιο εξεζητημένη ταξινόμηση με συγχώνευση για ταινίες (και δίσκους) που βελτιστοποιεί τη χρήση της ταινίας (και του δίσκου) είναι η πολυφασική ταξινόμηση με συγχώνευση.
Βελτιστοποίηση ταξινόμησης με συγχώνευση
Στους μοντέρνους υπολογιστές, η τοπικότητα της αναφοράς μπορεί να είναι μεγάλης σημασίας για τη βελτιστοποίηση του λογισμικού, επειδή χρησιμοποιούνται πολυεπίπεδες ιεραρχίες μνήμης. Έχουν προταθεί εκδόσεις του αλγορίθμου που εκμεταλλεύονται την λανθάνουσα μνήμη, οι οποίες αποτελούνται από εντολές βελτιστοποιημένες για την μετακίνηση σελίδων μέσα και έξω από τη λανθάνουσα μνήμη. Για παράδειγμα, η 'ταξινόμηση με συγχώνευση σε τμήματα' σταματάει τον κατακερματισμώ των υπολιστών όταν φτάσει σε υπολίστες μεγέθους S, όπου S ο αριθμός των στοιχείων δεδομένων που χωράνε στην λανθάνουσα μνήμη της Κεντρικής Μονάδας Επεξεργασίας. Κάθε μία από αυτές τις υπολίστες ταξινομείται με έναν επιτόπου αλγόριθμο ταξινόμησης, ώστε να αποδευχθούν οι αντιμεταθέσεις μνήμης, και κατόπιν η τυπική ταξινόμηση με συγχώνευση αναλαμβάνει με τη γνωστή αναδρομική μέθοδο. Αυτός ο αλγόριθμος έχει αποδειχθεί να αποδίδει καλύτερα σε μηχανές που επωφελούνται από την βελτιστοποίηση με λανθάνουσα μνήμη. (LaMarca & Ladner 1997)
Ο Kronrod (1969) πρότεινε μια εναλλακτική έκδοση της ταξινόμησης με συγχώνευση η οποία χρησιμοποιεί σταθερή πρόσθετη μνήμη. Ο αλγόριθμος αυτός αργότερα βελτιώθηκε. (Katajainen, Pasanen & Teuhola 1996).
Επίσης, πολλές εφαρμογές της εξωτερικής ταξινόμησης χρησιμοποιεί μια μορφή ταξινόμησης με συγχώνευση όπου η είσοδος διαχωρίζεται σε έναν αριθμό υπολιστών, για τον οποίον αριθμό, στην ιδανική περίπτωση, η συγχώνευση επιτρέπει το τρέχον σύνολο επεξεργασίας να χωράει στην κύρια μνήμη.
Παράλληλη επεξεργασία
Η ταξινόμηση με συγχώνευση αποτελεί καλή περίπτωση αλγορίθμου ως προς τη δυνατότητά του να εκτελεσθεί παράλληλα, εξαιτίας της μεθόδου διαίρει και βασίλευε που χρησιμοποιεί. Μια παράλληλη υλοποίηση υπάρχει γραμμένη σε ψευδοκώδικα στην τρίτη έκδοση του Introduction to Algorithms των Cormen, Leiserson, και Stein .[6] Αυτός ο αλγόριθμος χρησιμοποιεί έναν παράλληλο αλγόριθμο συγχώνευσης ώστε να εκτελέσει παράλληλα όχι μόνο την αναδρομική διαίρεση του πίνακα, αλλά και την λειτουργία της συγχώνευσης. Αποδίδει καλά στην πράξη όταν συνδυάζεται με μια γρήγορη ευσταθή σειριακή ταξινόμηση, όπως η ταξινόμηση με εισαγωγή και με μια γρήγορη σειριακή συγχώνευση σαν βάση για τη συγχώνευση μικρών πινάκων.[7] Η ταξινόμηση με συγχώνευση ήταν ένας από τους πρώτους αλγορίθμους ταξινόμησης όπου επετεύχθη μια βέλτιστη αύξηση της ταχύτητας, με τον Richard Cole να χρησιμοποιεί έναν έξυπνο αλγόριθμο υποδειγματοληψίας ώστε να καταφέρει συγχώνευση με κόστος O(1).[8] Άλλοι εξεζτητημένοι παράλληλοι αλγόριθμοι ταξινόμησης μπορούν να επιτύχουν τα ίδια ή καλύτερα χρονικά όρια με χαμηλότερη σταθερά. Για παράδειγμα, το 1991 ο David Powers περιέγραψε μια παράλληλη έκδοση της quicksort (και μια σχετική "radix sort") που τρέχει σε χρόνο O(log n) σε ένα CRCW PRAM με n επεξεργαστές εκτελώντας τον κατακερματισμό των πινάκων εσωτερικά.[9]
Σύγκριση με άλλους αλγορίθμους ταξινόμησης
Παρόλο που η ταξινόμηση με σωρό έχει τα ίδια χρονικά φράγματα με την ταξινόμηση με συγχώνευση, απαιτεί μόνο Θ(1) βοηθητικό χώρο, σε σύγκριση με την ταξινόμηση με συγχώνευση, και είναι συχνά γρηγορότερη σε πρακτικές εφαρμογές. Στις τυπικές μοντέρνες αρχιτεκτονικές, οι αποδοτικές υλοποιήσεις της ταχείας ταξινόμησης είναι ταχύτερες της ταξινόμησης με συγχώνευση στην ταξινόμηση πινάκων που βρίσκονται στην κεντρική μνήμη. Από την άλλη μεριά, η ταξινόμηση με συγχώνευση είναι ευσταθής συγχώνευση, υλοποιείται καλύτερα ώς προς τον παραλληλισμό, και είναι πιο αποδοτική στον χειρισμό σειριακών μέσων με αργή προσπέλαση. Η ταξινόμηση με συγχώνευση είναι συνήθως η καλύτερη επιλογή για την ταξινόμηση μιας συνδεδεμένης λίστας: σε αυτήν την περίπτωση είναι σχετικά εύκολο να υλοποιηθεί μια ταξινόμηση με συγχώνευση με τρόπο τέτοιο που να απαιτεί μόνο Θ(1) επιπλέον χώρο, και η χαμηλή απόδοση τυχαίας προσπέλασης της συνδεδεμένης λίστας κάνει κάποιους αλγορίθμους (όπως της ταχείας ταξινόμησης) να μην αποδίδουν ικανοποιητικά, ενώ κάποιοι άλλοι (όπως η ταξινόμηση με σωρό) είναι αδύνατο να υλοποιηθούν.
Από την Perl 5.8, η ταξινόμηση με συγχώνευση είναι ο προεπιλεγμένος αλγόριθμος με συγχώνευση (στις πρηγούμενες εκδόσεις της Perl ήταν η ταχεία ταξινόμηση). Στην Java, οι Arrays.sort() χρησιμοποιούν την ταξινόμηση με συγχώνευση ή μια βελτιωμένη ταχεία ταξινόμηση, σε συνάρτηση με τους τύπους των δεδομένων και για λόγους απόδοσης της υλοποίησης αλλάζουν σε ταξινόμηση με εισαγωγή όταν ταξινομούνται λιγότερα από επτά στοιχεία.[10] Η Python χρησιμοποιεί την timsort, μια άλλη βελτιωμένη υβριδική έκδοση της ταξινόμησης με συγχώνευση και της ταξινόμησης με εισαγωγή, η οποία επίσης έγινε η προεπιλεγμένη μέθοδος ταξινόμησης για την Java SE 7.[11]
Χρησιμότητα στην ταξινόμηση στο Διαδίκτυο
Η λειτουργία της συγχώνευσης στην ταξινόμηση με συγχώνευση είναι χρήσιμη στην ταξινόμηση στο Διαδίκτυο, όπου η λίστα προς ταξινόμηση λαμβάνεται στοιχείο προς στοιχείο, αντί να ληφθεί ολόκληρη από την αρχή. Σε αυτήν την εφαρμογή, ταξινομούμε κάθε νέο στοιχείο που λαμβάνουμε χρησιμοποιώντας οποιονδήποτε αλγόριθμο ταξινόμησης, και μετά το συγχωνεύουμε στην μέχρι στιγμής ταξινομημένη μας λίστα χρησιμοποιώντας τη λειτουργία της συγχώνευσης. Ωστόσο, η προσέγγιση αυτή μπορεί να αποδειχθεί ακριβή σε χρόνο και χώρο εάν τα δεδομένα λαμβάνονται σε μικρά τμήματα σε σχέση με την ταξινομημένη λίστα — μια καλύτερη προσέγγιση σε αυτήν την περίπτωση είναι η εισαγωγή των στοιχείων σε ένα δυαδικό δένδρο αναζήτησης τη στιγμή που λαμβάνονται.
Σημειώσεις
Knuth (1998, p. 158)
Jyrki Katajainen and Jesper Larsson Träff (1997). A meticulous analysis of mergesort programs.
Ο αριθμός για την χειρότερη περίπτωση που αναφέρεται εδώ δεν συμφωνεί με αυτόν που δίνεται στο έργο του Donald Knuth Art of Computer Programming, Vol 3. Η ασυμφωνία οφείλεται στο ότι ο Knuth ανέλυσε μία παραλλαγμένη υλοποίηση της ταξινόμησης με συγχώνευση, η οποία είναι λίγο λιγότερο αποδοτική.
«Μια υλοποίηση της επί τόπου ευσταθούς συγχώνευσης με ταξινόμηση σε Java». Αρχειοθετήθηκε από το πρωτότυπο στις 3 Φεβρουαρίου 2014. Ανακτήθηκε στις 4 Φεβρουαρίου 2012.
Selection sort. Knuth's snowplow. Natural merge.
Cormen και άλλοι 2009, σελ. 803
V. J. Duvanenko, "Parallel Merge Sort", Dr. Dobb's Journal, Μάρτιος 2011
Cole, Richard (August 1988). «Parallel merge sort». SIAM J. Comput. 17 (4): 770–785. doi:10.1137/0217049
Powers, David M. W. Parallelized Quicksort and Radixsort with Optimal Speedup, Proceedings of International Conference on Parallel Computing Technologies. Novosibirsk. 1991.
OpenJDK Subversion[νεκρός σύνδεσμος]
«Αρχειοθετημένο αντίγραφο». Αρχειοθετήθηκε από το πρωτότυπο στις 28 Φεβρουαρίου 2012. Ανακτήθηκε στις 4 Φεβρουαρίου 2012.
Αναφορές
Katajainen, Jyrki; Pasanen, Tomi; Teuhola, Jukka (1996). «Practical in-place mergesort». Nordic Journal of Computing 3: σελ. 27–40. ISSN 1236-6064. Αρχειοθετήθηκε από το πρωτότυπο στις 2011-08-07. Ανακτήθηκε στις 2009-04-04. Also Practical In-Place Mergesort. Also [1]
Knuth, Donald (1998). «Section 5.2.4: Sorting by Merging». Sorting and Searching. The Art of Computer Programming. 3 (2nd έκδοση). Addison-Wesley. σελίδες 158–168. ISBN 0-201-89685-0.
Kronrod, M. A. (1969). «Optimal ordering algorithm without operational field». Soviet Mathematics - Doklady 10: σελ. 744
LaMarca, A.; Ladner, R. E. (1997). «The influence of caches on the performance of sorting». Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA97): 370–379
Sun Microsystems, Inc. «Arrays API». Ανακτήθηκε στις 19 Νοεμβρίου 2007.
Sun Microsystems, Inc. «java.util.Arrays.java». Ανακτήθηκε στις 19 Νοεμβρίου 2007.[νεκρός σύνδεσμος]
Εξωτερικοί σύνδεσμοι
Animated Sorting Algorithms: Merge Sort – γραφική αναπαράσταση και συζήτηση για την ταξινόμηση με συγχώνευση των πινάκων
Dictionary of Algorithms and Data Structures: Merge sort
Hellenica World - Scientific Library
Από τη ελληνική Βικιπαίδεια http://el.wikipedia.org . Όλα τα κείμενα είναι διαθέσιμα υπό την GNU Free Documentation License
