Why “Merge Sort” better for linked lists ? And Why “Quick Sort” better for array ?
Why “Quick Sort” better for array ?
For array quicksort is much efficient than merge sort because, one of the main sources of efficiency in quicksort is locality of reference, which makes easy for the computer to access the memory locations that are near to each other tends to be faster than memory locations scattered throughout memory. The partitioning step in quicksort. Typically has excellent locality, since it accesses consecutive array elements near the front and the back. So, quicksort is better than all other sorting algorithms.
Additionally, quicksort is much faster because, it is in-place sort which means without needing to create any auxiliary arrays to hold temporary values. For arrays, merge sort loses due to the use of extra O(N) storage space.
Why “Merge Sort” better for linked lists ?
In linked lists cells are often scattered throughout memory, there is no locality bonus to accessing adjacent linked list cells, which is one of the most important advantage for huge performance of quick sort.the benefits of working in-place no longer apply, since merge sort’s linked list algorithm doesn’t need any extra auxiliary storage space,merge operation of merge sort can be implemented without extra space for linked lists.
Quick sort is fast in linked lists but, merge sort is faster because it more evenly splits the lists in half and does less work (In partitioning step).