Merge sort for Linked List.

Problem: Sort the given linked list using merge sort.

Why merge sort is preferred over quick sort in case of linked list?

In case of linked lists merge sort is preferred due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes are not  adjacent in memory. Unlike array, in 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 extra space for linked lists.

In arrays, we can do random access as elements are continuous in memory. Unlike arrays, we can not do random access in linked list. 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 continuous block of memory. Therefore, the overhead increases for quick sort. Merge sort accesses data sequentially and the need of random access is low.

Implementation:

//Public interface

void List::merge_sort()

{

if(head)

merge_sort(head);

}

void List::split(List::ListNode *source, ListNode *&front, ListNode *&back)

{

if(!source || !source->next)

{

front = source;

back = NULL;

return;

}

ListNode *fast = source->next, *slow = source;

while(fast != NULL)

{

fast = fast->next;

if(fast)

{

slow = slow->next;

fast = fast->next;

}

}

front = source;

back = slow->next;

slow->next = NULL;

}

List::ListNode* List::merge(List::ListNode *front, List::ListNode *back)

{

if(!front)

return back;

if(!back)

return front;

ListNode *final = 0;

if(front->data <= back->data)

{

final = front;

final->next = merge(front->next, back);

}

else

{

final = back;

final->next = merge(front, back->next);

}

return final;

}

void List::merge_sort(List::ListNode*& node)

{

if(!node || !node->next)

return;

ListNode *front = 0, *back = 0;

split(node, front, back);

merge_sort(front);

merge_sort(back);

node = merge(front, back);

}

Complexity: O(nlogn)