how does mergesort work with linked list code example
Example: merge sort in linked list
Merge_Sort(head_reference)
STEP 1: If head is NULL or there is only one element in the Linked List
then return the Linked List
STEP 2: Divide the linked list into two equal halves.
Split_Linked_List(head, &first_half, &second_half);
STEP 3: Sort the two halves first_half and second_half.
MergeSort(first_half);
MergeSort(second_half);
STEP 4: Merge the sorted first_half and second_half (using Merge_Sort() recursively)
and update the head pointer using head_reference.
*head_reference = Merge_Sort(first_half, second_half);