One of the main sources of efficiency in quicksort is the locality of the link , where computer hardware is optimized, so accessing memory locations that are next to each other is usually faster than accessing memory cells scattered throughout memory. The separation step in quicksort usually has excellent locality because it accesses the sequential elements of the array near the front and back sides. As a result, quicksort tends to work much better than other sorting algorithms such as heapsort, although it often makes about the same number of comparisons and swaps, since in the case of heapsort the calls are more scattered.
In addition, quicksort is usually much faster than other sorting algorithms because it works in place, without the need to create auxiliary arrays to store temporary values. Compared to something like merge sorting, this can be a huge advantage, since the time required to allocate and free auxiliary arrays can be noticeable. On-site operation also improves the location of quick sorting.
When working with linked lists, none of these benefits apply. Since linked list cells are often scattered throughout memory, there is no location bonus to access neighboring linked list cells. Consequently, one of the fast-growing huge performance benefits is being eaten. Similarly, the benefits of working in place are no longer applied, since the merge sort matching algorithm does not require additional additional storage space.
However, quicksort is still very fast on linked lists. Merge sorting tends to be faster because it more evenly splits lists in half and does less work on iterating for merging than for the splitting stage.
Hope this helps!
templatetypedef
source share