Merge sort is also one of the 'divide & conquer' classes of algorithms. The fundamental idea in it is to split the list in a number of sublists, sort each of these sublists & merge them to get a single sorted list. The descriptive implementation of 2 way merge sort sees the input initially as n lists of size 1. These are merged to acquire n/2 lists of size

2. These n/2 lists are merged pair wise and so on until a single list is obtained. It can be better understood by the following instance. This is also called Concatenate sort. Figure 2 illustrate 2-way merge sort.

Merge sort is the best method for sorting linked lists within random order. The total computing time is of the 0(n log₂n ).

The drawback of using mergesort is that it requires two arrays of the similar size & space for the merge phase. That is, to sort a list of size n, it requires space for 2n elements.

Figure: 2-way .merge sort

Mergesort is the greatest method for sorting linked lists into random order. The total computing time is of the 0(n log₂n ).

The drawback of using mergesort is that it needs two arrays of the similar size and space for the merge phase. That is, to sort a list of size n, it requires space for 2n elements.