Why is merge sort a better option than quicksort for linked lists? – InterviewSolution

InterviewSolution

1.	Why is merge sort a better option than quicksort for linked lists?
Answer» When it comes to linked lists, there are a few things to keep in mind. The issue is unique due to the memory allocation differences between arrays and linked lists. Unlike arrays, linked list nodes in memory may not be adjacent. We can insert items in the MIDDLE of a linked list in O(1) extra space and O(1) time if we are GIVEN a reference/pointer to the previous node, unlike an array. As a result, the merge SORT operation can be accomplished WITHOUT the need for additional linked list space. We can do random access in arrays since the elements are continuous in memory. In contrast to arrays, we can't access a linked list at random. Quick Sort necessitates a great deal of this type of access. Because we don't have a continuous block of memory, we have to travel from the head to the i'th node to get to the i'th index in a linked list. Merge sort accesses data in a sequential manner, with less requirement for random access.

Discussion

No Comment Found

Related InterviewSolutions

A given linked list is sorted based on absolute values. Write a function to sort the list based on actual values in O(n) time.
Given a linked list and a number n, you have to find the sum of the last n nodes of the linked list in a single traversal. Explain your approach in brief.
How will you modify a linked list of integers so that all even numbers appear before all odd numbers in the modified linked list? Also, keep the even and odd numbers in the same order.
A linked list of coordinates is given, with neighboring points forming either a vertical or horizontal line. Remove points in between the starting and ending points of the horizontal or vertical line from the linked list.
Construct a doubly linked list out of a ternary tree.
The task is to determine pairs in a doubly-linked list whose sum equals the provided value ‘val’ without consuming any extra space for a given sorted doubly-linked list of positive distinct entries. The expected complexities are O(n) time and O(1) space.
Given a 2-D matrix. You need to convert it into a linked list matrix such that each node is linked to its next right and down node and display it.
Extract all leaves from a Binary Tree into a Doubly Linked List (DLL).
Write a program to delete all odd positioned nodes from a circular linked list. (Consider 1-based indexing).
Why is merge sort a better option than quicksort for linked lists?