Home Java Beginners Arrayexamples Merge Sort Java
Questions:Ask|Latest


 
 

Share on Google+Share on Google+

Merge Sort Java

Advertisement
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 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 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

Advertisement

Liked it!  Share this Tutorial


Follow us on Twitter, or add us on Facebook or Google Plus to keep you updated with the recent trends of Java and other open source platforms.

Posted on: May 9, 2013

Ask Questions?    Discuss: Merge Sort Java  

Post your Comment


Your Name (*) :
Your Email :
Subject (*):
Your Comment (*):
  Reload Image
 
 
Comments
DMCA.com