Merge and Radix Sorts

Merge Sort

Merge Sort is a process of combining more than one sorted files into a single sorted file. The procedure is to divide a file of size n into n sub files of size 1 each. Now combine each adjacent sub files to form a set of n/2 sub files. Sort each sub files. Now merge adjacent sub files to form n/4 sub files and repeat the same process until a sorted file of size n is obtained.

Efficiency of Merge Sort

The algorithm for Merge sort requires almost logn passes and each pass requires n comparisons. Thus the Merge sort has the order O(nlogn) in both average and worst cases. Merge sort requires additional O(n) space for aux array.

Radix Sort

Radix sort is based on the sorting of a set of numbers according to the position values of digits. Suppose the set of numbers have n digits. The 1st phase of sort is to sort the numbers according to the units’ digits. The second phase would be to sort the above sorted file according to the tenth digits and so on until sorting with the most significant digit is done. The resulting file will be a sorted file.

Efficiency of Radix Sort

For a file of size n and m digits of each member, the order is O(mxn) or  O(nlogn) for the best case and O(n²) for the worst case.