Perché quicksort è migliore di un mergesort?

Mi è stata fatta questa domanda durante un’intervista. Sono entrambi O (nlogn) eppure la maggior parte delle persone usa Quicksort invece di Mergesort. Perché?

Quicksort ha runtime di caso O ( n 2 ) nel caso peggiore e tempo di esecuzione medio di O ( n log n ). Tuttavia, è preferibile unire l’ordinamento in molti scenari poiché molti fattori influenzano il runtime di un algoritmo e, quando li prende tutti insieme, Quicksort vince.

In particolare, il runtime spesso citato degli algoritmi di ordinamento fa riferimento al numero di confronti o al numero di swap necessari per eseguire l’ordinamento dei dati. Questa è davvero una buona misura delle prestazioni, soprattutto perché è indipendente dal design hardware sottostante. Tuttavia, anche altre cose, come la localizzazione di riferimento (cioè leggiamo molti elementi che sono probabilmente in cache?) Svolgono anche un ruolo importante sull’hardware attuale. Quicksort in particolare richiede poco spazio aggiuntivo ed esibisce una buona localizzazione della cache, e in molti casi questo rende più veloce dell’ordinamento dell’unione.

Inoltre, è molto facile evitare il tempo di esecuzione di O ( n 2 ) nel caso peggiore di quicksort quasi interamente utilizzando una scelta appropriata del pivot, come ad esempio selezionarlo a caso (questa è una strategia eccellente).

In pratica, molte implementazioni moderne di quicksort (in particolare std::sort libstdc ++) sono in realtà introsort , il cui caso peggiore è O ( n log n ), come merge sort. Ciò si ottiene limitando la profondità di ricorsione e passando a un algoritmo diverso ( heapsort ) una volta superato il log n .

Come molte persone hanno notato, la performance media dei casi per quicksort è più veloce di un mergesort. Ma questo è vero solo se stai assumendo un tempo costante per accedere a qualsiasi pezzo di memoria su richiesta.

Nella RAM questa ipotesi generalmente non è male (non è sempre vera a causa delle cache, ma non è male). Tuttavia, se la tua struttura dati è abbastanza grande da vivere su disco, Quicksort viene ucciso dal fatto che il tuo disco medio fa qualcosa come 200 ricerche casuali al secondo. Ma quello stesso disco non ha problemi a leggere o scrivere megabyte al secondo di dati in sequenza. Che è esattamente ciò che fa il mergesort.

Quindi, se i dati devono essere ordinati su disco, si vuole davvero usare qualche variazione su mergesort. (In genere, i quicksort si sottolineranno, quindi inizieranno a unirli insieme sopra una soglia di dimensione.)

Inoltre, se devi fare qualsiasi cosa con set di dati di quella dimensione, pensa seriamente a come evitare di cercare sul disco. Ad esempio, questo è il motivo per cui si consiglia di eliminare gli indici prima di eseguire grandi carichi di dati nei database e quindi ribuild l’indice in un secondo momento. Mantenere l’indice durante il caricamento significa cercare costantemente sul disco. Al contrario, se si rilasciano gli indici, il database può ribuild l’indice innanzitutto ordinando le informazioni da trattare (utilizzando un mergesort, ovviamente!) E quindi caricandolo in una infrastruttura BTREE per l’indice. (I BTREE sono naturalmente tenuti in ordine, quindi è ansible caricarne uno da un set di dati ordinato con poche ricerche su disco.)

Ci sono state diverse occasioni in cui capire come evitare la ricerca di dischi mi ha permesso di fare in modo che i lavori di elaborazione dati richiedessero ore anziché giorni o settimane.

In realtà, QuickSort è O (n 2 ). Il tempo medio di esecuzione del caso medio è O (nlog (n)), ma il suo caso peggiore è O (n 2 ), che si verifica quando lo si esegue in un elenco che contiene pochi elementi univoci. La randomizzazione richiede O (n). Naturalmente, questo non cambia il suo caso peggiore, ma impedisce solo a un utente malintenzionato di fare in modo che il tuo tipo richieda molto tempo.

QuickSort è più popolare perché:

  1. È sul posto (MergeSort richiede memoria aggiuntiva lineare al numero di elementi da ordinare).
  2. Ha una piccola costante nascosta.

Gli Algoritmi di ordinamento animati mostrano un numero di algoritmi su 4 diverse condizioni iniziali (casuali, quasi ordinate, invertite, poche uniche) e potrebbero aiutare.

“eppure la maggior parte delle persone usa Quicksort invece di Mergesort. Perché è così?”

Una ragione psicologica che non è stata data è semplicemente che Quicksort è più abilmente chiamato. cioè buon marketing.

Sì, Quicksort con tripla partioning è probabilmente uno dei migliori algoritmi di ordinamento general purpose, ma non c’è modo di superare il fatto che l’ordinamento “Quick” suona molto più potente di “Merge” sort.

Come altri hanno notato, il caso peggiore di Quicksort è O (n ^ 2), mentre mergesort e heapsort rimangono su O (nlogn). Nel caso medio, tuttavia, tutti e tre sono O (nlogn); quindi sono per la stragrande maggioranza dei casi comparabili.

Ciò che rende Quicksort migliore in media è che il ciclo interno implica il confronto di diversi valori con uno singolo, mentre negli altri due entrambi i termini sono diversi per ciascun confronto. In altre parole, Quicksort fa la metà delle letture degli altri due algoritmi. Nelle moderne CPU, le prestazioni sono pesantemente dominate dai tempi di accesso, quindi alla fine Quicksort finisce per essere un’ottima prima scelta.

Vorrei aggiungere quello dei tre algoritmi menzionati finora (mergesort, quicksort e heap sort) ma solo il mergesort è stabile. Cioè, l’ordine non cambia per quei valori che hanno la stessa chiave. In alcuni casi questo è desiderabile.

Ma, a dire il vero, in situazioni pratiche molte persone hanno bisogno solo di buone prestazioni medie e quicksort è … veloce =)

Tutti gli algoritmi di ordinamento hanno i loro alti e bassi. Vedi l’ articolo di Wikipedia per gli algoritmi di ordinamento per una buona panoramica.

Mu! Quicksort non è migliore, è adatto per un diverso tipo di applicazione, rispetto a un mergesort.

La Mergesort merita di essere presa in considerazione se la velocità è essenziale, le prestazioni peggiori nel caso peggiore non possono essere tollerate e lo spazio extra è disponibile. 1

Hai dichiarato che loro «Sono entrambi O (nlogn) […]». Questo è sbagliato. «Quicksort utilizza i confronti n ^ 2/2 nel caso peggiore.» 1 .

Tuttavia la proprietà più importante secondo la mia esperienza è la facile implementazione dell’accesso sequenziale che è ansible utilizzare durante l’ordinamento quando si utilizzano i linguaggi di programmazione con il paradigma imperativo.

1 Sedgewick, Algoritmi

Quicksort è l’algoritmo di ordinamento più veloce in pratica, ma ha un numero di casi patologici che possono farlo funzionare male come O (n2).

Heapsort è garantito per l’esecuzione in O (n * ln (n)) e richiede solo una memoria aggiuntiva finita. Ma ci sono molte citazioni di test del mondo reale che mostrano che heapsort è significativamente più lento di Quicksort in media.

Dalla voce di Wikipedia su Quicksort :

Quicksort compete anche con mergesort, un altro algoritmo di ordinamento ricorsivo ma con il vantaggio del tempo di esecuzione worst (nlogn) nel caso peggiore. Il Mergesort è un ordinamento stabile, a differenza di quicksort e heapsort, e può essere facilmente adattato per operare su elenchi collegati e elenchi molto grandi memorizzati su supporti ad accesso lento come lo storage su disco o l’archiviazione collegata alla rete. Sebbene Quicksort possa essere scritto per operare su liste collegate, spesso soffrirà di scarse opzioni di pivot senza accesso casuale. Lo svantaggio principale di mergesort è che, quando si opera su array, richiede Θ (n) spazio ausiliario nel migliore dei casi, mentre la variante di quicksort con partizionamento sul posto e ricorsione in coda utilizza solo lo spazio Θ (logn). (Si noti che quando si opera su liste collegate, il mergesort richiede solo una piccola quantità costante di memoria ausiliaria).

La spiegazione di Wikipedia è:

Tipicamente, quicksort è significativamente più veloce nella pratica rispetto ad altri algoritmi Θ (nlogn), perché il suo ciclo interno può essere implementato in modo efficiente su molte architetture e nella maggior parte dei dati del mondo reale è ansible fare scelte progettuali che minimizzano la probabilità di richiedere il tempo quadratico .

quicksort

mergesort

Penso che ci siano anche problemi con la quantità di memoria necessaria per Mergesort (che è Ω (n)) che le implementazioni Quicksort non hanno. Nel peggiore dei casi, hanno la stessa quantità di tempo algoritmico, ma il mergesort richiede più spazio di archiviazione.

Quicksort NON è migliore di un mergesort. Con O (n ^ 2) (il caso peggiore che accade raramente), quicksort è potenzialmente molto più lento di O (nlogn) dell’ordinamento di fusione. Quicksort ha meno spese generali, quindi con computer piccoli e lenti, è meglio. Ma oggi i computer sono così veloci che il sovraccarico aggiuntivo di un mergesort è trascurabile, e il rischio di un quicksort molto lento supera di gran lunga l’insignificante overhead di un mergesort nella maggior parte dei casi.

Inoltre, un mergesort lascia elementi con chiavi identiche nel loro ordine originale, un utile attributo.

Vorrei aggiungere alle grandi risposte esistenti alcuni elementi matematici su come QuickSort si comporta quando divergono dal caso migliore e quanto è probabile che sia, il che spero aiuterà le persone a capire un po ‘meglio perché il caso O (n ^ 2) non sia reale preoccupazione nelle implementazioni più sofisticate di QuickSort.

Al di fuori dei problemi di accesso casuale, vi sono due fattori principali che possono influire sulle prestazioni di QuickSort e sono entrambi correlati al modo in cui il pivot si confronta con i dati ordinati.

1) Un piccolo numero di chiavi nei dati. Un set di dati con lo stesso valore verrà ordinato in n ^ 2 volta su un QuickSort vaniglia a 2 partizioni perché tutti i valori tranne la posizione di pivot vengono posizionati su un lato ogni volta. Le moderne implementazioni affrontano questo problema con metodi come l’uso di un ordinamento a 3 partizioni. Questi metodi vengono eseguiti su un set di dati con lo stesso valore in tempo O (n). Pertanto, l’utilizzo di tale implementazione implica che un input con un numero limitato di chiavi migliora effettivamente il tempo di esecuzione e non rappresenta più un problema.

2) La selezione del perno estremamente pessima può causare prestazioni nel caso peggiore. In un caso ideale, il pivot sarà sempre tale che il 50% dei dati è più piccolo e il 50% dei dati è più grande, in modo tale che l’input sarà spezzato a metà durante ogni iterazione. Questo ci dà n confronti e tempi di scambio log-2 (n) ricorsioni per O (n * logn) tempo.

Quanto influisce la selezione del perno non ideale sul tempo di esecuzione?

Consideriamo un caso in cui il pivot viene scelto in modo coerente in modo che il 75% dei dati si trovi su un lato del pivot. È ancora O (n * logn) ma ora la base del log è cambiata in 1 / 0.75 o 1.33. La relazione in termini di prestazioni quando si cambia base è sempre una costante rappresentata da log (2) / log (newBase). In questo caso, quella costante è 2.4. Quindi questa qualità della scelta del perno richiede 2,4 volte più a lungo dell’ideale.

Quanto velocemente peggiora?

Non molto veloce fino a quando la scelta pivot diventa (costantemente) molto negativa:

  • 50% su un lato: (custodia ideale)
  • 75% su un lato: 2,4 volte il più lungo
  • 90% su un lato: 6,6 volte il tempo
  • 95% su un lato: 13,5 volte più lungo
  • 99% su un lato: 69 volte più lungo

Quando ci avviciniamo al 100% su un lato, la porzione di registro dell’esecuzione si avvicina a n e l’intera esecuzione si avvicina asintoticamente a O (n ^ 2).

In un’implementazione ingenua di QuickSort, casi come un array ordinato (per il primo elemento pivot) o un array ordinato in ordine inverso (per l’ultimo pivot dell’elemento) producono in modo affidabile un tempo di esecuzione O (n ^ 2) nel caso peggiore. Inoltre, le implementazioni con una selezione pivot prevedibile possono essere sottoposte all’attacco DoS da parte di dati progettati per produrre l’esecuzione nel caso peggiore. Le moderne implementazioni lo evitano con una varietà di metodi, come randomizzare i dati prima di ordinare, scegliere la mediana di 3 indici scelti casualmente, ecc. Con questa randomizzazione nel mix, abbiamo 2 casi:

  • Piccolo set di dati. Il caso peggiore è ragionevolmente ansible ma O (n ^ 2) non è catastrofico perché n è abbastanza piccolo che n ^ 2 è anche piccolo.
  • Grande set di dati. Il caso peggiore è ansible in teoria ma non nella pratica.

Quanto possiamo vedere prestazioni terribili?

Le probabilità sono incredibilmente piccole . Consideriamo una sorta di 5.000 valori:

La nostra ipotetica implementazione sceglierà un pivot usando una mediana di 3 indici scelti a caso. Considereremo i perni compresi nell’intervallo 25% -75% come “buoni” e i perni compresi nell’intervallo 0% -25% o 75% -100% per essere “non validi”. Se si guarda alla distribuzione di probabilità usando la mediana di 3 indici casuali, ciascuna ricorsione ha una probabilità di 11/16 di finire con un buon pivot. Facciamo 2 ipotesi conservative (e false) per semplificare la matematica:

  1. I buoni perni sono sempre esattamente al 25% / 75% divisi e funzionano a un caso ideale di 2,4 *. Non otteniamo mai una divisione ideale o uno split migliore di 25/75.

  2. I pivot sbagliati sono sempre i peggiori e non contribuiscono sostanzialmente alla soluzione.

La nostra implementazione di QuickSort si fermerà a n = 10 e passerà a un ordinamento di inserzione, quindi abbiamo bisogno di 22 partizioni pivot del 25% / 75% per interrompere il valore di 5.000 input fino a quel punto. (10 * 1.333333 ^ 22> 5000) Oppure, abbiamo bisogno di 4990 pivot nel caso peggiore. Tieni presente che se accumuliamo 22 buoni pivot in qualsiasi momento, l’ordinamento verrà completato, quindi la peggiore delle ipotesi o qualsiasi altra cosa che ci si avvicini richiede estremamente sfortuna. Se ci sono volute 88 ricorsioni per ottenere effettivamente i 22 buoni pivot necessari per ordinare fino a n = 10, sarebbe 4 * 2.4 * caso ideale o circa 10 volte il tempo di esecuzione del caso ideale. Quanto è probabile che non raggiungeremo i 22 buoni pivot necessari dopo 88 ricorsioni?

Le distribuzioni di probabilità binomiale possono rispondere a questo, e la risposta è circa 10 ^ -18. (n è 88, k è 21, p è 0,6875) Il tuo utente è circa un migliaio di volte più probabilità di essere colpito da un fulmine nel 1 secondo necessario per fare clic su [SORT] di quello che sono per vedere che 5.000 elementi sort peggio di peggio di 10 * caso ideale. Questa possibilità si riduce man mano che il set di dati diventa più grande. Ecco alcune dimensioni di array e le relative probabilità di funzionare più a lungo di 10 * ideale:

  • Matrice di 640 elementi: 10 ^ -13 (richiede 15 buoni punti di rotazione su 60 tentativi)
  • Matrice di 5.000 articoli: 10 ^ -18 (richiede 22 buoni pivot su 88 tentativi)
  • Matrice di 40.000 articoli: 10 ^ -23 (richiede 29 buoni pivot su 116)

Ricorda che questo è con 2 ipotesi conservative che sono peggiori della realtà. Quindi le prestazioni effettive sono ancora migliori e il saldo della probabilità rimanente è più vicino all’ideale che non.

Infine, come altri hanno menzionato, anche questi casi assurdamente improbabili possono essere eliminati passando a un ordinamento heap se lo stack di ricorsione è troppo profondo. Quindi il TLDR è che, per le buone implementazioni di QuickSort, il caso peggiore in realtà non esiste perché è stato progettato e l’esecuzione è completata nel tempo O (n * logn).

La risposta sarebbe leggermente inclinata verso quicksort wrt ai cambiamenti portati con DualPivotQuickSort per i valori primitivi. È usato in JAVA 7 per ordinare in java.util.Arrays

 It is proved that for the Dual-Pivot Quicksort the average number of comparisons is 2*n*ln(n), the average number of swaps is 0.8*n*ln(n), whereas classical Quicksort algorithm has 2*n*ln(n) and 1*n*ln(n) respectively. Full mathematical proof see in attached proof.txt and proof_add.txt files. Theoretical results are also confirmed by experimental counting of the operations. 

Puoi trovare l’impiantazione JAVA7 qui: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/7-b147/java/util/Arrays.java

Ulteriore lettura fantastica su DualPivotQuickSort – http://permalink.gmane.org/gmane.comp.java.openjdk.core-libs.devel/2628

Mentre sono entrambi nella stessa class di complessità, ciò non significa che entrambi abbiano lo stesso runtime. Quicksort è solitamente più veloce di un mergesort, solo perché è più facile codificare un’implementazione ristretta e le operazioni che esegue possono andare più velocemente. È perché quel quicksort è generalmente più veloce che le persone lo usano invece di un mergesort.

Però! Personalmente userò spesso mergesort o una variante quicksort che degrada a mergesort quando quicksort fa male. Ricorda. Quicksort è solo O (n log n) in media . Il caso peggiore è O (n ^ 2)! Il Mergesort è sempre O (n log n). Nei casi in cui le prestazioni in tempo reale o la reattività sono un must ei tuoi dati di input potrebbero provenire da una fonte malevola, non dovresti usare quicksort semplice.

Quicksort ha una complessità del caso medio migliore ma in alcune applicazioni è la scelta sbagliata. Quicksort è vulnerabile agli attacchi denial of service. Se un utente malintenzionato può scegliere l’input da ordinare, può facilmente build un set che impiega la complessità temporale più grave di o (n ^ 2).

La complessità media del caso di Mergesort e la complessità del caso peggiore sono le stesse, e come tale non subiscono lo stesso problema. Questa proprietà di merge-sort lo rende anche la scelta migliore per i sistemi in tempo reale, proprio perché non ci sono casi patologici che lo fanno funzionare molto, molto più lentamente.

Sono un fan più grande di Mergesort di quanto lo sia io di Quicksort, per queste ragioni.

A parità di condizioni, mi aspetterei che la maggior parte delle persone utilizzi ciò che è più facilmente disponibile e che tende ad essere qsort (3). A parte questo quicksort è noto per essere molto veloce sugli array, proprio come il mergesort è la scelta comune per le liste.

Quello che mi chiedo è perché sia ​​così raro vedere radix o bucket sort. Sono O (n), almeno nelle liste collegate e tutto ciò che serve è un metodo per convertire la chiave in un numero ordinale. (gli archi e i galleggianti funzionano bene).

Penso che la ragione abbia a che fare con il modo in cui viene insegnata l’informatica. Ho perfino dovuto dimostrare al mio docente di Algorithm Analysis che era effettivamente ansible ordinare più velocemente di O (n log (n)). (Aveva la prova che non è ansible eseguire il confronto con l’ ordinamento più veloce di O (n log (n)), che è vero).

In altre notizie, i float possono essere ordinati come numeri interi, ma devi girare i numeri negativi in ​​seguito.

Modifica: in realtà, ecco un modo ancora più vizioso per ordinare i float-as-interi: http://www.stereopsis.com/radix.html . Si noti che il trucco del bit-flipping può essere utilizzato indipendentemente da quale algoritmo di ordinamento effettivamente si usa …

È difficile da dire. Il peggiore di MergeSort è n (log2n) -n + 1, che è accurato se n equivale a 2 ^ k (l’ho già dimostrato). E per ogni n, è tra (n lg n -n + 1) e (n lg n + n + O (lg n)). Ma per quickSort, il suo migliore è nlog2n (anche n è uguale a 2 ^ k). Se dividi Mergesort per quickSort, equivale a uno quando n è infinito. è come se il caso peggiore di MergeSort sia migliore del caso migliore di QuickSort, perché usiamo quicksort? Ma ricorda, MergeSort non è a posto, richiede 2n di spazio memeroy. E MergeSort deve anche fare molte copie di array, che noi non includere nell’analisi dell’algoritmo. In una parola, MergeSort è davvero più faseter di quicksort in theroy, ma in realtà è necessario considerare lo spazio memeory, il costo della copia dell’array, la fusione è più lenta di un ordinamento rapido. Una volta ho fatto un esperimento in cui mi è stato dato 1000000 cifre in java dalla class Random, e ci sono voluti 2610ms di mergesort, 1370ms di quicksort.

Perché Quicksort è buono?

  • QuickSort prende N ^ 2 nel caso peggiore e nel caso medio NlogN. Il caso peggiore si verifica quando i dati vengono ordinati. Questo può essere mitigato da casuale casuale prima di iniziare l’ordinamento.
  • QuickSort non prende la memoria aggiuntiva che viene acquisita dall’ordinamento di unione.
  • Se il set di dati è grande e ci sono elementi identici, la complessità di Quicksort si riduce utilizzando la partizione a 3 vie. Più il numero di oggetti identici è migliore del genere. Se tutti gli elementi sono identici, ordina in tempo lineare. [Questa è l’implementazione predefinita nella maggior parte delle librerie]

Quicksort è sempre migliore di Mergesort?

Non proprio.

  • Mergesort è stabile ma Quicksort non lo è. Quindi se hai bisogno di stabilità in uscita, useresti Mergesort. La stabilità è richiesta in molte applicazioni pratiche.
  • La memoria è a buon mercato al giorno d’oggi. Quindi, se la memoria extra utilizzata da Mergesort non è fondamentale per la tua applicazione, non c’è nulla di male nell’uso di Mergesort.

Nota: in java, la funzione Arrays.sort () utilizza Quicksort per i tipi di dati primitivi e Mergesort per i tipi di dati dell’object. Poiché gli oggetti consumano sovraccarico della memoria, quindi l’aggiunta di un piccolo overhead per Mergesort potrebbe non rappresentare un problema per il punto di vista delle prestazioni.

Riferimento : guarda i video QuickSort della settimana 3, Corso Princeton Algorithms a Coursera

L’ordinamento rapido è il caso peggiore O (n ^ 2), tuttavia, il caso medio esegue in modo coerente l’ordinamento di tipo merge. Ogni algoritmo è O (nlogn), ma è necessario ricordare che quando si parla di Big O si eliminano i fattori di complessità inferiori. L’ordinamento rapido ha notevoli miglioramenti rispetto all’ordinamento di tipo merge quando si tratta di fattori costanti.

L’ordinamento unione richiede anche la memoria O (2n), mentre l’ordinamento rapido può essere eseguito in posizione (richiede solo O (n)). Questo è un altro motivo per cui l’ordinamento rapido è generalmente preferito rispetto all’unione di tipo merge.

Informazioni extra:

Il caso peggiore di ordinamento rapido si verifica quando il pivot viene scelto in modo errato. Considera il seguente esempio:

[5, 4, 3, 2, 1]

Se il pivot viene scelto come il numero più piccolo o più grande del gruppo, l’ordinamento rapido verrà eseguito in O (n ^ 2). La probabilità di scegliere l’elemento che si trova nel 25% più big o più piccolo della lista è 0,5. Ciò fornisce all’algoritmo una probabilità di 0,5 di essere un buon pivot. Se utilizziamo un tipico algoritmo di scelta del pivot (diciamo scegliendo un elemento casuale), abbiamo 0,5 possibilità di scegliere un buon pivot per ogni scelta di un pivot. Per le collezioni di grandi dimensioni, la probabilità di scegliere sempre un pivot povero è 0,5 * n. Sulla base di questa probabilità, l’ordinamento rapido è efficiente per il caso medio (e tipico).

In merge-sort, l’algoritmo generale è:

  1. Ordina l’array secondario sinistro
  2. Ordina il sub-array giusto
  3. Unisci i 2 sotto-array ordinati

Al livello più alto, la fusione dei 2 sottosegmenti ordinati comporta la gestione di N elementi.

Ad un livello inferiore a quello, ogni iterazione del passaggio 3 implica il trattamento di elementi N / 2, ma è necessario ripetere questo processo due volte. Quindi hai ancora a che fare con 2 * N / 2 == N elementi.

Un livello inferiore a quello, stai unendo 4 * N / 4 == N elementi, e così via. Ogni profondità nello stack ricorsivo comporta l’unione dello stesso numero di elementi, attraverso tutte le chiamate per quella profondità.

Considera invece l’algoritmo di ordinamento rapido:

  1. Scegli un punto di svolta
  2. Posiziona il punto di rotazione nella posizione corretta nell’array, con tutti gli elementi più piccoli a sinistra e gli elementi più grandi a destra
  3. Ordina il subarray sinistro
  4. Ordina il subarray di destra

Al livello più alto, hai a che fare con un array di dimensioni N. Scegli quindi un punto di rotazione, mettilo nella sua posizione corretta e puoi quindi ignorarlo completamente per il resto dell’algoritmo.

Un livello inferiore a quello, hai a che fare con 2 sotto-array che hanno una dimensione combinata di N-1 (cioè, sottrarre il punto pivot precedente). Scegli un punto di articolazione per ogni sub-array, che arriva a 2 ulteriori punti di rotazione.

Ad un livello inferiore, hai a che fare con 4 sotto-array con dimensioni combinate N-3, per gli stessi motivi di cui sopra.

Quindi N-7 … Quindi N-15 … Quindi N-32 …

La profondità della tua pila ricorsiva rimane approssimativamente la stessa (logN). With merge-sort, you’re always dealing with a N-element merge, across each level of the recursive stack. With quick-sort though, the number of elements that you’re dealing with diminishes as you go down the stack. For example, if you look at the depth midway through the recursive stack, the number of elements you’re dealing with is N – 2^((logN)/2)) == N – sqrt(N).

Disclaimer: On merge-sort, because you divide the array into 2 exactly equal chunks each time, the recursive depth is exactly logN. On quick-sort, because your pivot point is unlikely to be exactly in the middle of the array, the depth of your recursive stack may be slightly greater than logN. I haven’t done the math to see how big a role this factor and the factor described above, actually play in the algorithm’s complexity.

When I experimented with both sorting algorithms, by counting the number of recursive calls, quicksort consistently has less recursive calls than mergesort. It is because quicksort has pivots, and pivots are not included in the next recursive calls. That way quicksort can reach recursive base case more quicker than mergesort.

Unlike Merge Sort Quick Sort doesn’t uses an auxilary space. Whereas Merge Sort uses an auxilary space O(n). But Merge Sort has the worst case time complexity of O(nlogn) whereas the worst case complexity of Quick Sort is O(n^2) which happens when the array is already is sorted.

Small additions to quick vs merge sorts.

Also it can depend on kind of sorting items. If access to items, swap and comparisons is not simple operations, like comparing integers in plane memory, then merge sort can be preferable algorithm.

For example , we sort items using network protocol on remote server.

Also, in custom containers like “linked list”, the are no benefit of quick sort.
1. Merge sort on linked list, don’t need additional memory. 2. Access to elements in quick sort is not sequential (in memory)

Something to consider is memory as well. Mergesort requires an additional array, say a “workspace array”. If your memory is barely big enough to store your original array, then mergesort will not work.

Quick sort is an in-place sorting algorithm, so its better suited for arrays. Merge sort on the other hand requires extra storage of O(N), and is more suitable for linked lists.

Unlike arrays, in liked list we can insert items in the middle with O(1) space and O(1) time, therefore the merge operation in merge sort can be implemented without any extra space. However, allocating and de-allocating extra space for arrays have an adverse effect on the run time of merge sort. Merge sort also favors linked list as data is accessed sequentially, without much random memory access.

Quick sort on the other hand requires a lot of random memory access and with an array we can directly access the memory without any traversing as required by linked lists. Also quick sort when used for arrays have a good locality of reference as arrays are stored contiguously in memory.

Even though both sorting algorithms average complexity is O(NlogN), usually people for ordinary tasks uses an array for storage, and for that reason quick sort should be the algorithm of choice.

EDIT: I just found out that merge sort worst/best/avg case is always nlogn, but quick sort can vary from n2(worst case when elements are already sorted) to nlogn(avg/best case when pivot always divides the array in two halves).

This is a pretty old question, but since I’ve dealt with both recently here are my 2c:

Merge sort needs on average ~ N log N comparisons. For already (almost) sorted sorted arrays this gets down to 1/2 N log N, since while merging we (almost) always select “left” part 1/2 N of times and then just copy right 1/2 N elements. Additionally I can speculate that already sorted input makes processor’s branch predictor shine but guessing almost all branches correctly, thus preventing pipeline stalls.

Quick sort on average requires ~ 1.38 N log N comparisons. It does not benefit greatly from already sorted array in terms of comparisons (however it does in terms of swaps and probably in terms of branch predictions inside CPU).

My benchmarks on fairly modern processor shows the following:

When comparison function is a callback function (like in qsort() libc implementation) quicksort is slower than mergesort by 15% on random input and 30% for already sorted array for 64 bit integers.

On the other hand if comparison is not a callback, my experience is that quicksort outperforms mergesort by up to 25%.

However if your (large) array has a very few unique values, merge sort starts gaining over quicksort in any case.

So maybe the bottom line is: if comparison is expensive (eg callback function, comparing strings, comparing many parts of a structure mostly getting to a second-third-forth “if” to make difference) – the chances are that you will be better with merge sort. For simpler tasks quicksort will be faster.

That said all previously said is true: – Quicksort can be N^2, but Sedgewick claims that a good randomized implementation has more chances of a computer performing sort to be struck by a lightning than to go N^2 – Mergesort requires extra space

In c/c++ land, when not using stl containers, I tend to use quicksort, because it is built into the run time, while mergesort is not.

So I believe that in many cases, it is simply the path of least resistance.

In addition performance can be much higher with quick sort, for cases where the entire dataset does not fit into the working set.

One of the reason is more philosophical. Quicksort is Top->Down philosophy. With n elements to sort, there are n! possibilities. With 2 partitions of m & nm which are mutually exclusive, the number of possibilities go down in several orders of magnitude. m! * (nm)! is smaller by several orders than n! alone. imagine 5! vs 3! *2!. 5! has 10 times more possibilities than 2 partitions of 2 & 3 each . and extrapolate to 1 million factorial vs 900K!*100K! vs. So instead of worrying about establishing any order within a range or a partition,just establish order at a broader level in partitions and reduce the possibilities within a partition. Any order established earlier within a range will be disturbed later if the partitions themselves are not mutually exclusive.

Any bottom up order approach like merge sort or heap sort is like a workers or employee’s approach where one starts comparing at a microscopic level early. But this order is bound to be lost as soon as an element in between them is found later on. These approaches are very stable & extremely predictable but do a certain amount of extra work.

Quick Sort is like Managerial approach where one is not initially concerned about any order , only about meeting a broad criterion with No regard for order. Then the partitions are narrowed until you get a sorted set. The real challenge in Quicksort is in finding a partition or criterion in the dark when you know nothing about the elements to sort. That is why we either need to spend some effort to find a median value or pick 1 at random or some arbitrary “Managerial” approach . To find a perfect median can take significant amount of effort and leads to a stupid bottom up approach again. So Quicksort says just a pick a random pivot and hope that it will be somewhere in the middle or do some work to find median of 3 , 5 or something more to find a better median but do not plan to be perfect & don’t waste any time in initially ordering. That seems to do well if you are lucky or sometimes degrades to n^2 when you don’t get a median but just take a chance. Any way data is random. right. So I agree more with the top ->down logical approach of quicksort & it turns out that the chance it takes about pivot selection & comparisons that it saves earlier seems to work better more times than any meticulous & thorough stable bottom ->up approach like merge sort. Ma