Regarding Q.5.Sort A List
Why quick sort and heap sort cannot sort a random linked list in lesser time as compared to merge sort?
unable to understand.
Quiz questions on linked list
In arrays, we can do random access as elements are at contiguous memory locations. But, this is not possible in case of a linked list as each node is assigned distributed memory locations.
Quick Sort requires a lot of this kind of access. In linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have a continuous block of memory. Therefore, the overhead increases for quick sort. Merge sort accesses data sequentially and the need for random access is low.
Also, in a linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore merge operation of merge sort can be implemented without the need of extra space for linked lists. But, array requires O(n) extra space.
Therefore, we prefer merge sort for linked list.
Hope, this would help.
Give a like if you are satisfied.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.