[Παίζει μουσική] 

DOUG LLOYD: Εντάξει, έτσι η συγχώνευση sort είναι ένα ακόμη αλγόριθμο ότι μπορούμε να χρησιμοποιήσουμε για να λύσουμε τα στοιχεία ενός πίνακα. Αλλά, όπως θα δούμε, ότι έχεις ένα πολύ θεμελιώδης διαφορά από το είδος επιλογής, φούσκα είδος, και ταξινόμηση με εισαγωγή που την καθιστούν πραγματικά πολύ έξυπνο. 

Η βασική ιδέα πίσω από τη συγχώνευση sort είναι να ταξινομήσετε τα μικρότερα συστοιχίες και στη συνέχεια συνδυάζουν εκείνες τις συστοιχίες μαζί, ή να συγχωνεύσει them-- εξ ου και η name-- σε ταξινομημένη σειρά. Ο τρόπος που το κάνει ταξινόμηση με συγχώνευση Αυτό είναι με τη μόχλευση ένα εργαλείο που ονομάζεται αναδρομή, η οποία είναι ό, τι θα πάμε να μιλάμε για σύντομα, αλλά δεν έχουμε πραγματικά μίλησε ακόμα. 

Εδώ είναι η βασική ιδέα πίσω από τη συγχώνευση του είδους. Ταξινόμηση το αριστερό μισό του πίνακα, υποθέτοντας το η είναι μεγαλύτερο από 1. Και τι εννοώ όταν λέω υποθέτοντας η είναι μεγαλύτερο από 1 είναι, Νομίζω ότι μπορούμε να συμφωνήσουμε ότι αν μια σειρά μόνο αποτελείται από ένα μόνο στοιχείο, αυτό είναι ταξινομημένο. Δεν πραγματικά ανάγκη να κάνει τίποτα για αυτό. Εμείς απλά να κηρύξει πρέπει να διευθετηθεί. Είναι μόνο ένα στοιχείο. 

Έτσι, ο ψευδοκώδικας, πάλι, είναι ταξινομήσετε το αριστερό μισό του πίνακα, τότε ταξινομήσετε το δεξί μισό του πίνακα, Στη συνέχεια τη συγχώνευση των δύο μισά μαζί. Τώρα, ήδη θα μπορούσε να είναι σκέψης, το είδος ακριβώς Ακούγεται σαν να είστε απωθώντας the-- δεν έχετε κάνει τίποτα στην πραγματικότητα. Λέτε ταξινομήσετε το αριστερό ήμισυ, να ταξινομήσετε το δεξί μισό, αλλά εσείς δεν λέτε μου πώς το κάνετε. 

Αλλά να θυμάστε ότι όσο μια συστοιχία είναι ένα ενιαίο στοιχείο, μπορούμε να κηρύξει ταξινομημένο. Στη συνέχεια, μπορούμε να τα συνδυάσουμε απλά μαζί. Και αυτό είναι στην πραγματικότητα η βασική ιδέα πίσω από τη συγχώνευση του είδους, είναι να το σπάσει, έτσι ώστε συστοιχίες σας είναι ένα μέγεθος. Και τότε θα ξαναχτίσουν από εκεί. 

Συγχώνευση είδος είναι σίγουρα ένα πολύπλοκο αλγόριθμο. Και είναι, επίσης, ένα μικρό περίπλοκο να απεικονίσει. Έτσι, ελπίζουμε, η οπτικοποίηση ότι εγώ, έχουμε εδώ θα σας βοηθήσει να ακολουθήσετε μαζί. Και εγώ θα προσπαθήσω το καλύτερό μου για να αφηγηθεί τα πράγματα και να προχωρήσει μέσα από αυτό το λίγο περισσότερο αργά από τις άλλες απλά για να πάρει ελπίζουμε το κεφάλι σας γύρω από τις ιδέες πίσω από το είδος συγχώνευσης. 

Έτσι έχουμε την ίδια σειρά, όπως η άλλα βίντεο διαλογή αλγόριθμο αν έχετε δει them-- μια σειρά έξι στοιχείο. Και κώδικας pseudocode μας εδώ είναι το είδος το αριστερό μισό, να ταξινομήσετε το δεξί μισό, συγχώνευση των δύο μισά μαζί. Ας πάρουμε λοιπόν αυτό το πολύ σκούρο κόκκινο τούβλο σειρά και να ταξινομήσετε το αριστερό μισό. 

Έτσι, προς το παρόν, θα πάμε να αγνοήσει τα πράγματα σχετικά με το δικαίωμα. Είναι εκεί, αλλά είμαστε όχι σε αυτό το στάδιο ακόμα. Δεν είμαστε στο είδος του δεξιό μισό του πίνακα. Είμαστε σε είδος το αριστερό μισο της συστοιχίας. Και μόνο για χάρη να είναι λίγο πιο σαφείς, ώστε να μπορώ να αναφερθώ σε ποιο στάδιο είμαστε σε, Πάω να αλλάξουν το χρώμα αυτού του συνόλου σε πορτοκαλί. Τώρα, είμαστε ακόμα να μιλάμε για το ίδιο αριστερό μισό του αρχικού πίνακα. Αλλά ελπίζω ότι με το να είναι σε θέση να αναφέρονται στα χρώματα των διαφόρων ειδών, αυτό θα κάνει λίγο πιο σαφές τι συμβαίνει εδώ. 

Εντάξει, έτσι τώρα έχουμε μια τρία σειράς στοιχείων. Πώς μπορούμε να λύσουμε το αριστερό ήμισυ του εν λόγω συστοιχία, η οποία εξακολουθεί να είναι αυτό το βήμα; Προσπαθούμε να λύσουμε το αριστερό το ήμισυ του κεραμιδί array-- το αριστερό ήμισυ του οποίου Έχω τώρα χρωματισμένα πορτοκαλί. 

Λοιπόν, θα μπορούσαμε να προσπαθήσουμε και επαναλάβετε αυτή τη διαδικασία. Έτσι, είμαστε ακόμα στο μέση προσπαθώντας να ταξινομήσετε το αριστερό μισό του πλήρους πίνακα. Το αριστερό ήμισυ του array, είμαι απλώς πρόκειται να αποφασίζει αυθαίρετα ότι το αριστερό μισό θα είναι μικρότερο από το δεξιό ήμισυ, γιατί συμβαίνει αυτό αποτελείται από τρία στοιχεία. 

Και έτσι Πάω να πω ότι η αριστερό ήμισυ του αριστερού μισο η συστοιχία είναι ακριβώς το στοιχείο πέντε. Πέντε, είναι ένα μόνο στοιχείο σειρά, ξέρουμε πώς να το ξεκαθαρίσουμε. Και έτσι πέντε είναι ταξινομημένο. Είμαστε ακριβώς πρόκειται να δηλώσει ότι. Είναι μια απλή συστοιχία στοιχείο. 

Έτσι, έχουμε τώρα την ταξινόμηση αριστερό μισό του αριστερού half-- ή μάλλον, έχουμε την ταξινόμηση αριστερό μισό του πορτοκαλιού. Έτσι τώρα, προκειμένου να ολοκληρωθεί ακόμα το αριστερό μισό της συνολικής συστοιχίας, θα πρέπει να ταξινομήσετε το δεξί μισό του πορτοκαλί, ή αυτά τα πράγματα. Πώς θα το κάνουμε αυτό; Λοιπόν, έχουμε μια σειρά δύο στοιχείων. Έτσι μπορούμε να λύσουμε το αριστερό μισό της συστοιχίας, το οποίο είναι δύο. Δύο είναι ένα ενιαίο στοιχείο. Έτσι είναι ταξινομημένο από προεπιλογή. Στη συνέχεια, μπορούμε να λύσουμε το δεξί μισό του τμήματος της συστοιχίας, το ένα. Αυτό είναι το είδος του από προεπιλογή. 

Αυτή είναι τώρα η πρώτη φορά έχουμε φτάσει σε ένα στάδιο συγχώνευσης. Έχουμε ολοκληρώσει, αν και είμαστε τώρα το είδος των ένθετων down-- και αυτό είναι το είδος του δύσκολη πράγμα με αναδρομή είναι, θα πρέπει να κρατήσει σας το κεφάλι για το πού βρισκόμαστε. Έτσι, έχουμε το είδος της αριστεράς μισο του τμήματος πορτοκαλιού. 

Και τώρα, είμαστε στη μέση της διαλογής το δεξί μισό του τμήματος πορτοκαλί. Και σε αυτή τη διαδικασία, είμαστε τώρα για να είναι στο στάδιο, συγχώνευση των δύο μισά μαζί. Όταν κοιτάξουμε τα δύο ημίχρονα της συστοιχίας, βλέπουμε δυο και ένα. Ποιο στοιχείο είναι μικρότερο; Ένα. 

Τότε ποιο στοιχείο είναι μικρότερο; Λοιπόν, αυτό είναι δύο ή τίποτα. Γι 'αυτό είναι δύο. Μέχρι τώρα, μόνο και μόνο για να πλαισιώσει και πάλι πού βρισκόμαστε σε αυτό το πλαίσιο, έχουμε την ταξινόμηση αριστερό μισό του πορτοκαλιού και το δεξί μισό της καταγωγής. Ξέρω ότι έχω αλλάξει τα χρώματα και πάλι, αλλά αυτό είναι όπου ήμασταν. Και ο λόγος που το έκανα αυτό είναι επειδή αυτή η διαδικασία είναι Θα συνεχίσουμε, επανάληψη προς τα κάτω. Έχουμε ταξινομημένο το αριστερό το ήμισυ του πρώην πορτοκαλί και το δεξί μισό του πρώην πορτοκαλί. 

Τώρα, θα πρέπει να συγχωνευθούν εκείνους δύο μισά μαζί πάρα πολύ. Αυτό είναι το βήμα που βρίσκεστε. Έτσι θεωρούμε ότι όλα τα στοιχεία που είναι τώρα το πράσινο, το αριστερό μισό του αρχικού πίνακα. Και έχουμε συγχωνεύσει εκείνους χρησιμοποιώντας την ίδια διαδικασία κάναμε για τη συγχώνευση δύο και πριν από ένα μόλις μια στιγμή. 

Το αριστερό μισό, το μικρότερο στοιχείο στο αριστερό μισό είναι πέντε. Το μικρότερο στοιχείο για το δεξί μισό είναι ένα. Ποια από αυτά είναι μικρότερο; Ένα. 

Το μικρότερο στοιχείο για το αριστερό μισό είναι πέντε. Το μικρότερο στοιχείο για το δεξί μισό είναι δύο. Ποια είναι η μικρότερη; Δύο. Και στη συνέχεια, τέλος, πέντε τίποτα, μπορούμε να πούμε πέντε. 

Εντάξει, έτσι μεγάλη εικόνα, ας να κάνουν ένα διάλειμμα για ένα δεύτερο και να καταλάβω πού βρισκόμαστε. Αν ξεκινήσαμε από η ίδια η αρχή, έχουν πλέον ολοκληρωθεί για η συνολική διάταξη μόνο ένα βήμα του κώδικα ψευδοκώδικα εδώ. Έχουμε ταξινομημένο το αριστερό ήμισυ της συστοιχίας. 

Υπενθυμίζεται ότι το αρχικό διαταγή ήταν πέντε, δύο, ένα. Με τη μετάβαση μέσω αυτής της διαδικασίας και φωλιάζουν κάτω και επανάληψη, συνεχίζοντας να σπάσει το πρόβλημα κάτω σε όλο και μικρότερα τμήματα, Έχουμε ολοκληρώσει τώρα Βήμα πρώτο του ψευδοκώδικα για ολόκληρης της συστοιχίας εκκίνησης. Έχουμε ταξινομημένο αριστερό ήμισυ της. 

Έτσι τώρα ας παγώσει εκεί. Και τώρα ας λύσουμε το δικαίωμα το μισό του αρχικού πίνακα. Και θα πάμε να το κάνουμε αυτό από διέρχεται από το ίδιο επαναληπτική διαδικασία της άρσης πράγματα κάτω και στη συνέχεια συγχώνευσή τους μαζί. 

Έτσι, το αριστερό ήμισυ του κόκκινο, ή το αριστερό ήμισυ του δικαιώματος μισό του αρχικού σειρά, Πάω να πω είναι τρεις. Και πάλι, είμαι συνεπείς εδώ. Εάν έχετε μια περίεργη αριθμός των στοιχείων του, Δεν έχει τόση σημασία αν κάνετε το αριστερό μικρότερα ή το δικαίωμα ενός μικρότερου. 

Αυτό που έχει σημασία είναι ότι κάθε φορά που αντιμετωπίσετε αυτό το πρόβλημα κατά τη διεξαγωγή των μια συγχώνευση, θα πρέπει να είναι συνεπής. Μπορείτε είτε πρέπει πάντα να κάνει μια αριστερή πλευρά μικρότερη ή πρέπει πάντα να κάνετε η δεξιά πλευρά μικρότερο. Εδώ, έχω επιλέξει να είναι πάντα κάνουν την αριστερή πλευρά μικρότερη όταν σειρά μου, ή μου υπο-πίνακα, είναι ένα περίεργο μέγεθος. 

Τρεις είναι ένα μόνο στοιχείο, και γι 'αυτό είναι ταξινομημένο. Έχουμε μόχλευση αυτή την υπόθεση καθ 'όλη τη διαδικασία μας μέχρι στιγμής. Έτσι τώρα ας λύσουμε το δικαίωμα μισό του δεξιού μισού, ή το δεξί μισό του κόκκινου. 

Και πάλι, θα πρέπει να χωρίσει αυτό κάτω. Αυτό δεν είναι ένα ενιαίο στοιχείο συστοιχία. Δεν μπορούμε να την κηρύξει ταξινομημένο. Και έτσι το πρώτο, θα πάμε για να ταξινομήσετε το αριστερό μισό. 

Το αριστερό μισό είναι ένα ενιαίο στοιχείο, έτσι είναι είδος από προεπιλογή. Στη συνέχεια, θα πάμε για να ταξινομήσετε τη σωστή ένα δεύτερο, το οποίο είναι ένα ενιαίο στοιχείο. Είναι ταξινομημένο ως προεπιλογή. Και τωρα, μπορούμε να συγχωνευθούν τα δύο αυτά μαζί. Τέσσερις είναι μικρότερο, και στη συνέχεια, έξι είναι μικρότερο. 

Και πάλι, τι έχουμε κάνει σε αυτό το σημείο; Έχουμε ταξινομημένο το αριστερό μισό του δεξιού μισού. Ή για να επανέλθω στο αρχικό χρώματα που υπήρχαν, έχουμε ταξινομημένο το αριστερό μισο του μαλακότερο κόκκινο. Ήταν αρχικά ένα σκοτεινό τούβλο κόκκινο και τώρα είναι μια πιο ήπια κόκκινο, ή ήταν ένα μαλακότερο κόκκινο. 

Και τότε έχουμε την ταξινόμηση δεξιό μισό του μαλακότερο κόκκινο. Τώρα, επίσης, ότι είναι πράσινα και πάλι, απλά επειδή είμαστε σε μια διαδικασία. Και πρέπει να επαναλάβουμε αυτό ξανά και ξανά. 

Έτσι τώρα μπορούμε να συγχωνεύσει εκείνους δύο μισά μαζί. Και αυτό είναι που κάνουμε εδώ. Έτσι, η μαύρη γραμμή μόνο διαιρείται το αριστερό μισό και το δεξί μισό του μέρους αυτού του είδους. 

Συγκρίνουμε τη μικρότερη τιμή στην αριστερή πλευρά της array-- ή με συγχωρείτε, το μικρότερο αξία του αριστερού μισο με την μικρότερη τιμή του δικαιώματος το ήμισυ και να διαπιστώσει ότι τρεις είναι μικρότερο. Και τώρα ένα κομμάτι από μια βελτιστοποίηση, σωστά; Δεν υπάρχει πραγματικά τίποτα αριστερά στην αριστερή πλευρά. 

Δεν υπάρχει τίποτα που απομένει στην αριστερή πλευρά, ώστε να μπορούμε αποτελεσματικά ακριβώς move-- μπορούμε να δηλώσουμε το υπόλοιπο είναι πραγματικά ταξινομούνται και απλά να αναστρέψει σχετικά, γιατί δεν υπάρχει τίποτα άλλο να συγκρίνετε με. Και γνωρίζουμε ότι η δεξιά πλευρά της δεξιάς πλευράς είναι ταξινομημένο. 

Εντάξει, έτσι και τώρα ας παγώσει και πάλι καταλάβουμε πού βρισκόμαστε στην ιστορία. Στη συνολική συστοιχία, τι έχουμε καταφέρει; Έχουμε πράγματι επιτύχει τώρα τα βήματα ένα και το δεύτερο βήμα. Εμείς ταξινομημένο το αριστερό μισό, και θα διευθετηθεί το δεξί μισό. 

Μέχρι τώρα, το μόνο που μας απομένει είναι για τη συγχώνευση αυτών των δύο μισά μαζί. Γι 'αυτό και το συγκρίνουμε με τη χαμηλότερη αξία στοιχείο κάθε μισό του πίνακα με τη σειρά του και να προχωρήσει. Ένα είναι μικρότερος των τριών, έτσι πηγαίνει. 

Δύο είναι μικρότερος των τριών, έτσι πηγαίνει δύο. Τρεις είναι μικρότερη από 5, οπότε τρεις πηγαίνει. Τέσσερις είναι μικρότερη από 5, έτσι ώστε τέσσερεις πηγαίνει. Στη συνέχεια, πέντε είναι μικρότερη των έξι, και έξι είναι το μόνο που απομένει. 

Τώρα, ξέρω, ότι ήταν πολλά βήματα. Και έχουμε άφησε πολλά της μνήμης στο πέρασμά μας. Και αυτό είναι ό, τι είναι αυτά τα γκρι τετράγωνα. Και μάλλον ένιωσα ότι πήρε πολύ περισσότερο από ό, τι είδος εισαγωγής, φούσκα είδος ή είδος επιλογής. 

Αλλά στην πραγματικότητα, επειδή ένας πολλά από αυτές τις διαδικασίες συμβαίνουν στο ίδιο time-- το οποίο είναι κάτι που θα, και πάλι, μιλάμε για όταν μιλάμε για αναδρομή σε μια μελλοντική video-- Αυτός ο αλγόριθμος πραγματικά σαφώς είναι θεμελιωδώς διαφορετική από οτιδήποτε άλλο έχουμε ξαναδεί αλλά είναι επίσης σημαντικά πιο αποτελεσματική. 

Γιατί αυτό? Λοιπόν, στη χειρότερη σενάριο, έχουμε να χωρίσει n στοιχεία μέχρι και στη συνέχεια ανασυνδυάζονται τους. Αλλά όταν εμείς ανασυνδυάζονται τους, αυτό που κάνουμε είναι βασικά ο διπλασιασμός μέγεθος των μικρότερων συστοιχιών. Έχουμε ένα σωρό ενός στοιχείου πινάκων που μπορούμε αποτελεσματικά συνδυάζονται σε δύο σειρές στοιχείων. Και τότε παίρνουμε εκείνες δυο σειρές στοιχείων και να τα συνδυάσετε σε τέσσερεις σειρές στοιχείων, και ούτω καθεξής, και ούτω καθεξής, και ούτω καθεξής, μέχρι να έχουν ένα ενιαίο πίνακα n στοιχείων. 

Αλλά πόσοι διπλασιασμούς χρειάζεται για να πάρει στο n; Σκεφτείτε πίσω στο παράδειγμα τηλεφωνικό κατάλογο. Πόσες φορές έχουμε να σχίσει τον τηλεφωνικό κατάλογο στη μέση, πόσα περισσότερα φορές έχουμε να σχίσει τον τηλεφωνικό κατάλογο στο μισό, αν το μέγεθος του τηλεφωνικού καταλόγου διπλασιαστεί; Υπάρχει μόνο ένα, έτσι δεν είναι; 

Έτσι, υπάρχει κάποιο είδος λογαριθμική στοιχείο εδώ. Αλλά πρέπει επίσης να εξακολουθούν να έχουν τουλάχιστον δείτε όλα τα n στοιχεία. Έτσι, στη χειρότερη περίπτωση, ταξινόμηση με συγχώνευση τρέχει στο n log n. Πρέπει να κοιτάξουμε όλα τα n στοιχεία, και πρέπει να τα συνδυάσουν μαζί log n σύνολα βημάτων. Στην καλύτερη περίπτωση, η σειρά είναι απόλυτα ταξινομημένο. Αυτό είναι υπέροχο. Όμως, με βάση τον αλγόριθμο που έχουμε εδώ, έχουμε ακόμη να χωρίσετε και ανασύνθεσης. Αν και στην περίπτωση αυτή, η ανασυνδυασμο είδους αναποτελεσματική. Δεν είναι απαραίτητη. Αλλά ακόμα περνάμε η όλη διαδικασία ούτως ή άλλως. 

Έτσι, στην καλύτερη περίπτωση και στη χειρότερη περίπτωση, Αυτός ο αλγόριθμος τρέχει σε n log n του χρόνου. Συγχώνευση είδος είναι σίγουρα λίγο πιο περίπλοκη από τις άλλες κύριες αλγορίθμων ταξινόμησης έχουμε μιλήσει για CS50, αλλά είναι αισθητά πιο ισχυρή. 

Και έτσι αν ποτέ βρείτε την ευκαιρία να το χρειαστείτε ή να το χρησιμοποιήσετε για να ταξινομήσετε ένα μεγάλο σύνολο δεδομένων, να πάρει το κεφάλι σας γύρω από την ιδέα της αναδρομής πρόκειται να είναι πραγματικά ισχυρή. Και αυτό πρόκειται να κάνει σας προγράμματα πραγματικά πολύ πιο αποδοτική χρησιμοποιώντας ταξινόμηση με συγχώνευση έναντι οτιδήποτε άλλο. Είμαι ο Νταγκ Lloyd. Αυτό είναι CS50.