Merge Sort

Merge Sort

Merge sort is an age-old sorting algorithm yet still being the one of the most efficient sorting algorithms, it was found in the late 1950s by Sir John von Neumann. It was one of the first algorithms which used the divide and conquer approach. The divide and conquer approach states that if you have a big problem then you just dive all those big problems into smaller problems and then find the solution to all those smaller problems and then combine all those solutions to get the solution of the final problem. It seems really easy and simple but sometimes it might be hard to implement.

The basic idea of merge sort is to divide the given array into atomic values i.e. till every element of the array is isolated, then compare those elements and form new sub arrays, then, in turn, merge those sub-arrays until we have the original array sorted. Basically, in merge sort we have two primary functions namely ‘MergeSort’ and the ’Merge’ function, the task of ‘MergeSort’ is to recursively divide the given array into halves of halves and after all, elements have been isolated, it passes them to the other ‘Merge’ function which them makes a new array, copies the values from both the arrays in a sorted fashion to the new-made array and lastly copies back the sorted elements to the original array.

The code for merge sort for an array data structure is mainstream, let’s then discuss the working of merge sort in Linked List data structure:

Here, this given code has three primary functions-

mergesort_ll — As this function is the recursive function it first checks if it has reached the final condition i.e., the linked list has been fully divided into single values, else it finds the middle node of the linked list with the help of a function called ‘mid_ll’ then it calls itself from head to middle node i.e. for the left half and then from the successor or the middle node to the tail node i.e. for the right half and then it passes these two halves to the function ‘merge_ll’ which will merge them. Hence passing the final sorted linked list to the main function.

Note: In the function ‘mergesort_ll’ after all the nodes have been isolated, after then only the function ‘merge_ll’ would be called.

merge_ll — This function accepts two linked lists and then creates a temporary linked list, then it traverses both of the accepted linked lists using two node pointers and puts the values in the temporary linked list in a sorted fashion and there are still more elements left in the accepted linked list, it again traverses then to finally validate that all the elements have been copied or not. After copying all the elements, it returns the merged linked list to the ‘mergesort_ll’ function.

mid_ll — This is a helper function used to compute the middle node of any given linked list. It uses a strategical technique where two node pointers are traversed in the given linked list and one of the pointers moves at 2x speed whereas other moves at normal 1x speed. Whenever the faster pointer reaches the end of the linked list, the other pointer always points at the middle node. Hence, the middle node is passed to the ‘mergesort_ll’ function.

The above three functions demonstrate the working of Merge sort in the linked list data structure.

The overall time complexity for these functions are as follows:

mid_ll — n/2≈O(n)

merge_ll — n≈ O(n)

mergesort_ll — T(n)=2T(n/2)+n/2+n≈O(nlogn)

Time Complexity of Merge sort

The overall time complexity of merge sort comes out to be O(nlogn) as the function ‘mergesort’ divides the array until all elements are isolated. Here is the tree.

The height of this tree is logn and for every recursive call, it also merges the sub-arrays which takes O(n) time. Hence the overall time complexity comes out to be O(nlogn). Therefore, Merge sort has no best or worst case scenarios because in every case it will divide the array irrespective of being sorted or not.

Space Complexity of Merge sort

A temporary array is required where we put the elements from the original array to this temporary array in a sorted fashion. Hence space complexity is: O(n)