Interview Question Software Engineer / Developers
I assume the question is for inplace sorting. because if extra memory is allowed then any efficient sort can be used.
Since we don't have direct indexing we cannot access an element directly and for merge sort we would require n additional pointers to each node (doesn't matter if it's by recursion). So we cannot use merge sort because it would require O(n) space. Maybe insertion sort is the best in for linked list, any suggestions?
Sorry, i guess you meant by recursion (mergesort). But even that takes additional space if i am not wrong.
@Kishore
No, it takes O(1) space.
Because unlike sorting an array using merge sort, there is no need for an auxiliary array when you're merging two linked list.
When you merge, you can just modify the pointer(reference) of the last element in the sorted list to point to the next element. All you need is to keep track of the last element in the sorted list, and the pointers to the two candidates for next element to be added.
To sort a linked list merge sort is good in comparison to other sorts because
1.QuickSort: In linked list choosing a pivot is not O(1) also arranging the elements against pivot is O(n^2).
2. Similar comparison can be drawn for other sorts on the basis of accessing an element in Araay (O(1)) and Linked list (O(n)).
Here, merging is in place and of O(n) at each level of recursion.
Although choosing mid is again not of O(1) as compare to array. Even though the time complexity is O(nlogn).
Apart from that with the use of extra space we can use generic Qsort function to sort.
e.g.
We can create an array of pointer of the nodes and sort this array with a compare function like
int compare_func(const void* node1, const void* node2)
{
const node* keyNode1 = (node*)node1;
const node* keyNode2 = (node*)node2;
return (keyNode1->data - keyNode2->data)
}
After sorting finishes we can re-make the list using this array.
Merge sort, because merge sort has worse case of O(nlogn) complexity (compring to O(n^2) for quick sort) and during the merge phase, you do not need to allocate extra memory like you have to for array.
- Anonymous February 23, 2011