Il punto di questa domanda non è di discutere i meriti di questo su qualsiasi altro algoritmo di ordinamento - certamente ci sono molte altre domande che lo fanno. Questa domanda riguarda il nome. Perché Quicksort viene chiamato "Quicksort"? Certo, è "veloce", la maggior parte delle volte, ma non sempre. La possibilità di degenerare a O (N ^ 2) è ben nota. Ci sono varie modifiche a Quicksort che mitigano questo problema, ma quelle che portano il caso peggiore a un O garantito (n log n) non sono generalmente chiamate Quicksort. (ad esempio Introsort).
Mi chiedo solo perché di tutti i ben noti algoritmi di ordinamento, questo è l'unico meritevole del nome "quick", che descrive non come funziona l'algoritmo, ma quanto è veloce (di solito). Mergesort è chiamato così perché unisce i dati. Heapsort viene chiamato così perché utilizza un heap. Introsort prende il nome da "Introspective", poiché monitora le proprie prestazioni per decidere quando passare da Quicksort a Heapsort. Allo stesso modo per tutti quelli più lenti - Bubblesort, Insertion sort, Selection sort, ecc. Sono tutti chiamati per come funzionano. L'unica altra eccezione che mi viene in mente è "Bogosort", che in realtà è solo uno scherzo che nessuno in realtà utilizza nella pratica. Perché Quicksort non ha chiamato qualcosa di più descrittivo, come "Partition sort" o "Pivot sort", che descrive cosa fa effettivamente? Non è nemmeno il caso di "prima arriva qui". Mergesort è stato sviluppato 15 anni prima di Quicksort. (1945 e 1960 rispettivamente secondo Wikipedia)
Immagino che questa sia davvero una questione di storia più che di programmazione. Sono solo curioso di sapere come è stato il nome - è stato solo un buon marketing?