External Sorting(Merge Sort)

 

Performance of merge sort:

Regardless of best or worst case, the number of swaps in this algorithm is always 2(last -first +1) per merge, where first and last are the indexes of the first and last items in the (sub)list, respectively. 

In the best case, where the list is sorted, the number of comparisons per pass is (first +last)/2. 

In the worst case, where the last item of one sublist precedes only the last item of the other sublist, the number of comparisons is last -first, which approaches N.

Thus, for the worst and average cases, the number of comparisons and number of swaps for merge sort is O(N log N ). 

In theory, merge sort is as fast as quicksort. In practice, however, merge sort performs a bit more slowly, because of all the data copying the algorithm requires.