Introduction

In today's article we discuss the Merge Sort using Java.

Merge Sort

The Merge Sort algorithm is based on a divide-and-conquer strategy. Merge Sorting was invented by John von Neumann in 1945. Its worst-case running time has a lower order of growth than an Insertion Sort. Here, we divide the array to be sorted into two halves, sort these two sub-arrays separately, and then combine (merge) these sorted sub-arrays to produce a solution to the original problem. For sorting the sub-arrays, we can use recursion. Since we are dealing with sub-problems, we state each subproblem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through sub-problems. In comparison to a Quicksort, the divide part is simple in a Merge Sort while the merging is complex. In addition a Quicksort can work "inline", for example, it does not need to create a copy of the collection while a Merge Sort requires a copy.
1. Divide Step
If a given array A has zero elements or one element then it simply returns; it is already sorted. Otherwise, partition the n-element sequence to be sorted into two subsequences of n/2 elements each.

2. Conquer Step
Sort the divided subsequences recursively using the Merge Sort.

3. Combine Step
Combine or merge the divided sorted subsequences, each to generate the sorted array consisting of n elements.
The following procedure shows how the data is sorted in a Merge Sort:
  1. If the list is of 1 in length, then the list is already sorted
  2. If the list size is more than 1, then divide the array list into two parts. (An odd-numbered length list can't be divided equally in two)
  3. Continue to divide the sub-lists until we get a data size of 1 in length
  4. Now merge the divided-lists back into a list double their size, at the same time sorting each item into the order
  5. Continue merging the divided lists until the full list is complete again
Advantages
  1. Stable performance
  2. It can be applied to files of any size
  3. Suited to sorting linked lists of elements because the merge traverses each linked list
  4. Suited to sorting external files; divides data into smaller files until can be stored in an array in memory
  5. Conceptually simple
Example
  1. public class MregeSortEx
  2. {
  3. public static void main(String a[])
  4. {
  5. //Numbers which are to be sorted
  6. int n[] = {124,23,43,12,177,25,2,1,67};
  7. //Displays the numbers before sorting
  8. System.out.print("Before sorting, numbers are ");
  9. for(int i = 0; i < n.length; i++)
  10. {
  11. System.out.print(n[i]+" ");
  12. }
  13. System.out.println();
  14. //Sorting in ascending order using bubble sort
  15. initializemergeSort(n,0,n.length-1);;
  16. //Displaying the numbers after sorting
  17. System.out.print("After sorting, numbers are ");
  18. for(int i = 0; i < n.length; i++)
  19. {
  20. System.out.print(n[i]+" ");
  21. }
  22. }
  23. //This method sorts the input array in asecnding order
  24. public static void initializemergeSort(int n[], int l, int h)
  25. {
  26. int low = l;
  27. int high = h;
  28. if (low>=high)
  29. {
  30. return;
  31. }
  32. int middle=(low+high)/2;
  33. initializemergeSort(n,low,middle);
  34. initializemergeSort(n,middle+1,high);
  35. int end_low=middle;
  36. int start_high=middle+1;
  37. while ((l<=end_low) && (start_high<=high))
  38. {
  39. if (n[low]<n[start_high])
  40. {
  41. low++;
  42. }
  43. else
  44. {
  45. int Temp=n[start_high];
  46. for (int k=start_high-1;k>=low;k--)
  47. {
  48. n[k+1]=n[k];
  49. }
  50. n[low]=Temp;
  51. low++;
  52. end_low++;
  53. start_high++;
  54. }
  55. }
  56. }
  57. }
Output
mergesort.jpg