Merge Sort Java

Merge Sort in Java is used to sort integer values of an array. There are many methods to sort Java like bubble sort, insertion sort, selection sort, etc. In Merge sort unsorted values are divided into two equal parts, then they are repeatedly merged till the final list is in sorted order completely.

Merge Sort Java

Merge Sort can be implemented in following ways:

Bottom-Up implementation
Top-Down Implementation
Left-Right Implementation
Tiled Implementation

Worst-case of Merge sort is O(n log n) and average case of Merge Sort is O(n log n).

Merge Sort is slow in comparison to heapsort and quicksort. But it is stable sort and is more efficient in sorting a LinkedList.

Following example shows the use of Merge sort in sorting an unsorted list.

At first the unsorted list is split in two-halves until each half has smallest element (a list of 1 element is considered sorted). Then compare each element in two halves with the adjacent list iteratively until the values are sorted.

In simple words, an unsorted list is divided into "n" sublists, each containing 1 element. The sublists are merged repeatedly until there is only 1 sorted list remaining.

Example of Merge Sort in Java

public class mergeSort{
  public static void main(String a[]){
  int i;
  int array[] = {73, 8, 25, 64, 4, 55, 98, 13};
  System.out.println("\n\n RoseIndia\n\n");
  System.out.println(" Selection Sort\n\n");
  System.out.println("Values Before the sort:\n");
  for(i = 0; i < array.length; i++)
  System.out.print( array[i]+"  ");
  System.out.println();
  mergeSort_srt(array,0, array.length-1);
  System.out.print("Values after the sort:\n");
  for(i = 0; i = high) {
  return;
  }

  int middle = (low + high) / 2;
  mergeSort_srt(array, low, middle);
  mergeSort_srt(array, middle + 1, high);
  int end_low = middle;
  int start_high = middle + 1;
  while ((lo <= end_low) && (start_high <= high)) {
  if (array[low] < array[start_high]) {
  low++;
  } else {
  int Temp = array[start_high];
  for (int k = start_high- 1; k >= low; k--) {
  array[k+1] = array[k];
  }
  array[low] = Temp;
  low++;
  end_low++;
  start_high++;
  }
  }
  }  
}

Output:

C:\array\sorting>javac mergeSort.java
C:\array\sorting>java mergeSort

RoseIndia
Selection Sort

Values Before the sort:
73 8 25 64 4 55 98 13

Values after the sort:
4 8 13 25 55 64 73 98

Merge Sort Java

Merge Sort Java

Tutorials