[RIPRODUZIONE DI BRANI MUSICALI] 

DOUG LLOYD: OK, così un'unione tipo è un altro algoritmo che possiamo usare per risolvere gli elementi di un array. Ma, come vedremo, che ha un differenza molto fondamentale dalla selezione tipo, bolla ordinamento e insertion sort che lo rendono davvero molto intelligente. 

L'idea di base dietro merge tipo è quello di ordinare le matrici più piccoli e poi combinare questi array insieme, o unire them-- da qui il nome-- in modo ordinato. Il modo in cui si fondono fa specie questo è sfruttando uno strumento chiamato ricorsione, che è ciò che stiamo andando a parlare di presto, ma non abbiamo ancora parlato ancora. 

Ecco l'idea di base dietro merge sort. Ordina la metà sinistra della matrice, supponendo n è maggiore di 1. E quello che intendo quando dico supponendo n è maggiore di 1 è, Penso che possiamo essere d'accordo che se una matrice soltanto costituito da un unico elemento, è ordinato. Noi in realtà non serve a tutto pur di esso. Possiamo solo dichiarare da ordinare. E 'solo un singolo elemento. 

Così pseudocodice, di nuovo, è ordinare la metà di sinistra della matrice, poi ordinare la metà destra della matrice, quindi unire le due metà insieme. Ora, già si potrebbe essere pensando, che tipo di solo suona come si sta mettendo fuori the-- non stai realmente facendo nulla. Stai dicendo che ordinare la sinistra la metà, ordinare la metà destra, ma tu non stai dicendo me come si sta facendo. 

Ma ricordate che finché un array è un singolo elemento, possiamo dichiarare che risolto. Allora possiamo solo combinarli insieme. E questo è in realtà il idea fondamentale dietro merge sort, è una scomposizione in modo che gli array sono di dimensioni uno. E poi si ricostruisce da lì. 

Merge sort è sicuramente un algoritmo complicato. Ed è anche un po ' complicato da visualizzare. Così si spera, la visualizzazione che io avete qui vi aiuterà a seguire insieme. E farò del mio meglio per raccontare le cose e procedere attraverso questo un po 'più lentamente rispetto gli altri solo per ottenere la vostra testa si spera intorno alle idee che stanno dietro merge sort. 

Così abbiamo la stessa matrice come il altri video algoritmo di ordinamento se avete visto them-- un array di sei elementi. E il nostro codice pseudocodice qui è sorta la metà di sinistra, ordinare la metà destra, unire le due metà insieme. Quindi cerchiamo di prendere questo rosso mattone molto scuro array e ordinare la metà di sinistra di esso. 

Così, per il momento, stiamo andando di ignorare le cose di destra. E 'lì, ma siamo non a ma questo passo. Non siamo in genere il metà destra della matrice. Siamo al sorta sinistra metà dell'array. E solo per il gusto di essere un po 'più chiaro, così posso fare riferimento a quale punto siamo su, Ho intenzione di cambiare la colore di questo insieme di arancio. Ora, stiamo ancora parlando della stessa metà sinistra della matrice originale. Ma spero che, essendo in grado di fare riferimento ai colori dei vari elementi, che ti farà un po 'più chiaro quello che sta succedendo qui. 

OK, ora abbiamo un tre schiera di elementi. Come si fa a ordinare la metà di sinistra di questo array, che è ancora questo passo? Stiamo cercando di risolvere la sinistra metà del array-- rosso mattone la metà sinistra di cui Ora ho di colore arancione. 

Beh, potremmo cercare di ripetere questo processo. Quindi siamo ancora in mezzo di cercare di ordinare la metà sinistra della matrice completa. La metà sinistra del array, sto solo andando decidere arbitrariamente che la metà sinistra sarà inferiore alla metà di destra, perché questo accade a costituita da tre elementi. 

E così ho intenzione di dire che la metà sinistra della metà sinistra della matrice è solo l'elemento cinque. Cinque, essendo un unico elemento array, sappiamo come risolverlo. E così cinque è ordinato. Stiamo solo andando a dichiarare che. Si tratta di un unico array elemento. 

Così ora abbiamo risolto il la metà sinistra del half-- sinistra o meglio, abbiamo risolto il metà sinistra arancione. Così ora, in modo da ancora completo metà sinistra della matrice globale, abbiamo bisogno di ordinare la metà destra del arancio, o questa roba. Come lo facciamo? Beh, abbiamo un array di due elementi. Così possiamo ordinare la metà di sinistra della matrice, che è due. Due è un singolo elemento. Quindi è ordinato per impostazione predefinita. Poi possiamo ordinare la metà destra di quella parte della matrice, quella. Questo è una sorta di default. 

Questo è ora la prima volta abbiamo raggiunto un passo di unione. Abbiamo completato, anche se ora stiamo tipo di annidati down-- e questo è una specie di difficile cosa con la ricorsione è, è necessario mantenere la vostra testa su dove ci troviamo. Così abbiamo sorta di sinistra la metà della porzione arancione. 

E ora, siamo nel bel mezzo di di smistamento la metà destra della porzione arancione. E in questo processo, siamo ora sta per essere sul gradino, unire le due metà insieme. Quando guardiamo le due metà dell'array, vediamo due e uno. Quale elemento è più piccolo? Uno. 

Allora quale elemento è più piccolo? Beh, è ​​due o nulla. Quindi è due. Così ora, solo per inquadrare di nuovo dove siamo nel contesto, abbiamo ordinato il metà sinistra del arancio e la metà destra dell'origine. So che ho cambiato i colori ancora una volta, ma che è dove siamo stati. E la ragione per cui ho fatto questo è perché questo processo è intenzione di andare avanti, l'iterazione giù. Abbiamo risolto il sinistro la metà del primo arancione e la metà destra del primo arancione. 

Ora, abbiamo bisogno di unire quelli due metà insieme troppo. Questo è il passo che siamo su. Così noi consideriamo tutto il elementi che sono ora verde, la metà sinistra della matrice originale. E ci fondiamo quelli utilizzando lo stesso processo abbiamo fatto per la fusione di due e uno appena un attimo fa. 

La metà sinistra, il più piccolo elemento sulla metà sinistra è cinque. Il più piccolo elemento la metà destra è uno. Quale di questi è più piccolo? Uno. 

Il più piccolo elemento la metà sinistra è cinque. Il più piccolo elemento la metà destra è due. Qual è il più piccolo? Due. E poi, infine, cinque e nulla, possiamo dire cinque. 

OK, così grande immagine, diamo prendersi una pausa per un secondo e capire dove siamo. Se siamo partiti Fin dall'inizio, abbiamo hanno ormai completato per la matrice complessiva appena un passo del codice pseudocodice qui. Abbiamo ordinato la metà sinistra della matrice. 

Ricordiamo che l'originale ordine era cinque, due, uno. Passando attraverso questo processo e nidificazione giù e ripetendo, continuando a rompere il problema in parti più piccole, abbiamo completato passo uno dei pseudocodice per l'intero array di partenza. Abbiamo ordinato la sua metà sinistra. 

Così ora cerchiamo di congelare lì. E ora diamo ordinare il giusto metà dell'array originale. E abbiamo intenzione di farlo da passando attraverso lo stesso iterativo processo di rompere le cose e quindi unendo insieme. 

Quindi la metà sinistra del rosso, o la metà sinistra della metà destra dell'originale array, ho intenzione di dire è di tre. Ancora una volta, devo essere coerente qui. Se si dispone di una strana numero di elementi, in realtà non importa se a fare la sinistra più piccolo o destra più piccola. 

Ciò che conta è che ogni volta che verificare questo problema nella conduzione una fusione, è necessario essere coerenti. Si sia sempre necessario fare una lato sinistro più piccolo o sempre bisogno di fare destra più piccola. Qui, ho scelto di sempre rendere il lato sinistro più piccolo quando la mia matrice, o il mio sub-array, è di una dimensione dispari. 

Tre è un singolo elemento, e così è ordinato. Abbiamo sfruttato questa ipotesi durante tutto il nostro processo finora. Così ora cerchiamo di ordinare il giusto metà della metà destra, o la metà destra del rosso. 

Ancora una volta, abbiamo bisogno di dividere questo in giù. Questo non è un singolo elemento dell'array. Non possiamo dichiarare risolto. E così prima, stiamo andando per ordinare la metà sinistra. 

La metà sinistra è un singolo elemento, quindi è una sorta di default. Poi andremo a ordinare la destra mezzo, che è un singolo elemento. E 'ordinato per impostazione predefinita. E adesso, possiamo unire quei due insieme. Four è più piccolo, e allora sei è più piccolo. 

Anche in questo caso, quello che abbiamo fatto a questo punto? Abbiamo risolto il sinistro metà della metà destra. O tornare a quella originale colori che erano lì, abbiamo risolto sinistra metà rosso morbido. In origine era un mattone scuro rosso e ora è un più morbido rosso, o che fosse un rosso morbido. 

E allora abbiamo risolto il metà destra rosso morbido. Ora, bene, sono di nuovo verde, appena perché noi stiamo attraversando un processo. E dobbiamo ripetere più e più. 

Così ora siamo in grado di unire quelli due metà insieme. E questo è quello che facciamo qui. Così la linea nera appena diviso la metà sinistra e la metà destra di questa parte tipo. 

Confrontiamo il valore più piccolo sul lato sinistro della array-- o mi scusi, la più piccola valore della metà sinistra al valore minimo del diritto mezzo e scoprire che tre è più piccolo. Ed ora un po 'di ottimizzazione, giusto? In realtà c'è niente sinistra sul lato sinistro. 

Non c'è niente rimanente sul lato sinistro, in modo che possiamo in modo efficiente solo move-- possiamo dichiarare il resto è effettivamente ordinati e appena virare essa su, perché non c'è niente altro da confrontare. E sappiamo che il lato destro del lato destro è ordinato. 

OK, ora cerchiamo di congelare di nuovo e capire dove siamo nella storia. Nella matrice complessiva, cosa abbiamo realizzato? Abbiamo effettivamente realizzare Ora passi uno e fase due. Abbiamo risolto la metà sinistra, e abbiamo risolto la metà destra. 

Così ora, tutto ciò che rimane è per noi di fondere queste due metà insieme. Quindi mettiamo a confronto il più basso valorizzati elemento di ciascuna metà della matrice a sua volta, e procedere. Uno è inferiore a tre, così si va. 

Due è inferiore a tre, così due va. Tre è inferiore a 5, quindi tre tentativi. Quattro è meno di 5, quindi quattro va. Poi cinque è inferiore a sei, e sei è tutto ciò che rimane. 

Ora, lo so, che era un sacco di passi. E abbiamo lasciato un sacco della memoria nella nostra scia. Ed è quello che i quadrati grigi sono. E probabilmente sembrava che ha preso un molto più lungo di insertion sort, bolla sorta, o la selezione sorta. 

Ma in realtà, perché un Molti di questi processi stanno accadendo allo stesso tempo-- che è qualcosa faremo, ancora una volta, parlare quando si parla di ricorsione in un futuro video-- questo algoritmo in realtà chiaramente è fondamentalmente diverso da qualsiasi cosa abbiamo visto prima ma è anche significativamente più efficiente. 

Come mai? Ebbene, nel peggiore ipotesi, abbiamo dividere n elementi su e poi ricombinare. Ma quando abbiamo ricombiniamo loro, quello che stiamo facendo è sostanzialmente raddoppiando la dimensioni delle matrici più piccole. Abbiamo un po 'di un elemento array che abbiamo effettivamente combinarle in due array di elementi. E poi prendiamo quelli due array di elementi e combinarli per creare quattro matrici elemento, e così via, e così via, e così via, fino a che avere un singolo elemento dell'array n. 

Ma quanti raddoppi ci vuole per arrivare a n? Ripensate all'esempio rubrica telefonica. Quante volte dobbiamo strappare la rubrica telefonica a metà, come molti altri volte dobbiamo strappare la rubrica telefonica a metà, se la dimensione della rubrica raddoppiato? C'è solo uno, giusto? 

Quindi c'è una sorta di elemento logaritmica qui. Ma abbiamo anche ancora almeno guarda tutti gli elementi n. Così, nel peggiore dei casi, merge sort viene eseguito in log n n. Dobbiamo guardare tutti gli n elementi, e dobbiamo combinarli insieme a log n rampe di scale. Nel migliore dei casi, la matrice è perfettamente ordinato. È fantastico. Ma in base all'algoritmo che abbiamo qui, dobbiamo ancora suddividere e ricombinare. Anche se in questo caso, la ricombinazione è una specie di inefficace. Non è necessario. Ma abbiamo ancora attraversiamo l'intero processo comunque. 

Quindi nel caso migliore e, nel caso peggiore, questo algoritmo viene eseguito in n log n tempo. Merge sort è sicuramente un po 'più complicato rispetto agli altri algoritmi di ordinamento principali abbiamo parlato di CS50 ma è sostanzialmente più potente. 

E così se mai trovare occasione di bisogno o usarlo per ordinare un grande insieme di dati, ottenendo la testa intorno all'idea di ricorsione sta per essere davvero potente. E sta andando a rendere la vostra programmi davvero molto più efficiente utilizzando merge sort contro qualsiasi altra cosa. Sono Doug Lloyd. Questo è CS50.