Java Program for Merge Sort using Recursion example.

Merge Sort uses divide and conquer algorithm. The unsorted list is divided into two equal sub lists.Then Sort each sub list using recursion by calling the merge sort function again. Finally Merge the two sub lists back into one sorted list. Go through the following example which uses Merge Sort to sort the unsorted list (7,5,3,1,2,6,2,4)

Merge Sort Code Starts


package net.javaonline;

import java.util.Scanner;

public class MergeSort{

  public static void main(String a[]){

  int temp;


Scanner sc=new Scanner (System.in);

System.out.println("Enter N ( how many numbers to be sorted)");

int n = sc.nextInt();


int [] list=new int[n];

System.out.println("Enter "+n+ " numbers 1 by 1");


for (int i=0 ; i<n; i++)

     {

     int  number = sc.nextInt();

     list[i]=number;

     }


  System.out.println("List before  sorting \n");

  for(int i = 0; i < list.length; i++)

	  System.out.print( list[i]+"  ");

  System.out.println();
  

  mergeSort(list,0, list.length-1);
  

  System.out.print("List after sorting \n");

  for(int i = 0; i < list.length; i++)

	  System.out.print(list[i]+"  ");

  System.out.println();

  }


  public static void mergeSort(int list[],int low, int high){

   if (low >= high) 
          { 
	           return;
	          }   


  int middle = (low + high) / 2;          

  mergeSort(list, low, middle);

  mergeSort(list, middle + 1, high);

  merge(list, low,middle,high);


       }


private static void merge(int list[], int low, int middle, int high)

{

  int IstList_end= middle;

  int IIndList_start = middle + 1;

  int l=low;

  while ((l <= IstList_end) && (IIndList_start <= high))

             {

	  if (list[low] < list[IIndList_start]) {

		  	low++;

	     } else {

			  int temp = list[IIndList_start];
	
			  for (int j = IIndList_start-1; j >= low; j--) {
	
			  list[j+1] = list[j];

		  }

	  list[low] = temp;

	  low++;

	  IstList_end++;

	  IIndList_start++;

	  }

    }


  }  

} 

You may also like

Leave a Reply

Be the First to Comment!