Merge Sort Program in Java

In this tutorial of Java Programming, we have implemented the Merge Sorting Algorithm to ssort the elements of a given array. In this Merge sort program, you can also edit the merge sort program code to get the elements of Array by user itself.

Merge Sort technique is a divide and conquer algorithm that was invented by John Von Neuman in 1945. Conceptually, a merge sort works as follows :

1. Divide the unsorted list into n sublists, each containing one element.

2. Repeatedly merge sub-lists to produce new sub-lists until there is only one sub list remaining.

Merge Sort Program Code in Java

public class MergeSort {

   static int[] array = {597, 21, 523, 1378, 243, 774, 14, 93, 510, 5, 67, 23};

   public static void mergeSort(int a[]) {
     int tmpArray[] = new int[a.length];
     mergeSort(a, tmpArray, 0, a.length-1);
   }

   private static void mergeSort(int a[], int tmpArray[], int left, int
right) {

     if (left < right) {
       int center = (left+right)/2;
       mergeSort(a, tmpArray, left, center);
       mergeSort(a, tmpArray, center+1, right);
       merge(a, tmpArray, left, center+1, right);
     }
   }

   private static void merge(int a[], int tmpArray[], int leftPos, int
rightPos, int rightEnd) {
     int leftEnd = rightPos-1;
     int tmpPos = leftPos;
     int numElements = rightEnd - leftPos + 1;

     while (leftPos <= leftEnd && rightPos <= rightEnd)
       if (a[leftPos] <= a[rightPos])
         tmpArray[tmpPos++] = a[leftPos++];
       else
         tmpArray[tmpPos++] = a[rightPos++];

     while (leftPos <= leftEnd)
       tmpArray[tmpPos++] = a[leftPos++];

     while (rightPos <= rightEnd)
       tmpArray[tmpPos++] = a[rightPos++];

     for (int i=0; i<numElements; i++, rightEnd--)
       a[rightEnd] = tmpArray[rightEnd];
   }

   public static void main(String args[]) {

     System.out.println("This is the array before Sorting: ");
     display(array);

     System.out.println("Array After merge sort...");
     mergeSort(array);
     display(array);

   }

   private static void display(int x[]) {
     for (int i=0; i<x.length; i++)
       System.out.print(x[i] + " ");
     System.out.println("\n");
   }
}

Output of Merge Sort Java Program 

 

Related Posts: