quick-sort although its ( )-time worst-case performance makes quick-sort susceptible in real-time applications where we must make guarantees on the time needed to complete sorting operationwe expect its performance to be ( log )-timeand experimental studies have shown that it outperforms both heap-sort and merge-sort on many tests quick-sort does not naturally provide stable sortdue to the swapping of elements during the partitioning step for decades quick-sort was the default choice for general-purposein-memory sorting algorithm quick-sort was included as the qsort sorting utility provided in language librariesand was the basis for sorting utilities on unix operating systems for many years it was also the standard algorithm for sorting arrays in java through version of that language (we discuss java below merge-sort merge-sort runs in ( log ntime in the worst case it is quite difficult to make merge-sort run in-place for arraysand without that optimization the extra overhead of allocate temporary arrayand copying between the arrays is less attractive than in-place implementations of heap-sort and quick-sort for sequences that can fit entirely in computer' main memory even somerge-sort is an excellent algorithm for situations where the input is stratified across various levels of the computer' memory hierarchy ( cachemain memoryexternal memoryin these contextsthe way that merge-sort processes runs of data in long merge streams makes the best use of all the data brought as block into level of memorythereby reducing the total number of memory transfers the gnu sorting utility (and most current versions of the linux operating systemrelies on multiway merge-sort variant since the standard sort method of python' list class has been hybrid approach named tim-sort (designed by tim peters)which is essentially bottom-up merge-sort that takes advantage of some initial runs in the data while using insertion-sort to build additional runs tim-sort has also become the default algorithm for sorting arrays in java bucket-sort and radix-sort finallyif an application involves sorting entries with small integer keyscharacter stringsor -tuples of keys from discrete rangethen bucket-sort or radix-sort is an excellent choicefor it runs in ( ( )timewhere [ is the range of integer keys (and for bucket sortthusif ( nis significantly "belowthe log functionthen this sorting method should run faster than even quick-sortheap-sortor merge-sort