elements)because insertion-sort is simple to programand small sequences necessarily have few inversions alsoinsertion-sort is quite effective for sorting sequences that are already "almostsorted by "almost,we mean that the number of inversions is small but the ( )-time performance of insertion-sort makes it poor choice outside of these special contexts merge-sort merge-sorton the other handruns in (nlogntime in the worst casewhich is optimal for comparison-based sorting methods stillexperimental studies have shown thatsince it is difficult to make merge-sort run in-placethe overheads needed to implement merge-sort make it less attractive than the in-place implementations of heap-sort and quick-sort for sequences that can fit entirely in computer' main memory area even somerge-sort is an excellent algorithm for situations where the input cannot all fit into main memorybut must be stored in blocks on an external memory devicesuch as disk in these contextsthe way that merge-sort processes runs of data in long merge streams makes the best use of all the data brought into main memory in block from disk thusfor external memory sortingthe merge-sort algorithm tends to minimize the total number of disk reads and writes neededwhich makes the merge-sort algorithm superior in such contexts quick-sort experimental studies have shown that if an input sequence can fit entirely in main memorythen the in-place versions of quick-sort and heap-sort run faster than merge-sort the extra overhead needed for copying nodes or entries puts mergesort at disadvantage to quick-sort and heap-sort in these applications in factquicksort tendson averageto beat heap-sort in these tests soquick-sort is an excellent choice as general-purposein-memory sorting algorithm indeedit is included in the qsort sorting utility provided in language libraries stillits ( time worst-case performance makes quick-sort poor choice in real-time applications where we must make guarantees on the time needed to complete sorting operation heap-sort in real-time scenarios where we have fixed amount of time to perform sorting operation and the input data can fit into main memorythe heap-sort algorithm is probably the best choice it runs in (nlognworst-case time and can easily be made to execute in-place