Java two way merge sort sample share

  • 2020-04-01 03:03:49
  • OfStack

Merge sort is sort by divide and conquer:

(1) divide an array into two small arrays for sorting respectively;

(2) after that, merge the separated arrays with a good order;


import java.util.Scanner;
public class MergeSort {
    int[] a=null;
    int[] b=null;
    int n;
    Scanner sin=null;

    MergeSort()
    {
        a=new int[10000];
        b=new int[10000];
        sin=new Scanner(System.in);
    }

    void sort(int start,int end)    //Sort a [start... end]
    {
        int mid;
     if(start >= end)    //When there is only one element, return
            return ;
        else
        {
            mid=(end-start)/2;    //Divide the elements in half and sort them separately
            sort(start,start+mid);
            sort(start+mid+1,end);

            //Merge two ordered arrays a[start...start+mid] and a[start+mid+1...end]
            merge(start,start+mid,end);    
        }
    }

    void merge(int start,int mid,int end)    //merge
    {
        int t=start;
        int i=start,j=mid+1;
        while(i<=mid && j<=end)
        {
            if(a[i]<a[j])
                b[t++]=a[i++];
            else
                b[t++]=a[j++];
        }
        while(i<=mid)
            b[t++]=a[i++];
        while(j<=end)
            b[t++]=a[j++];

        for(i=start;i<=end;i++)    //The sorted contents are written back to the corresponding position in the a array
            a[i]=b[i];
    }

    void run()
    {
        System.out.print(" Enter the number of Numbers to be sorted: ");
        n=sin.nextInt();
        for(int i=0;i<n;i++)
            a[i]=sin.nextInt();
        sort(0,n-1);
        System.out.println(" The sorting results are: ");
        //Enter the data to be sorted
        for(int i=0;i<n;i++)
            System.out.println(a[i]+"  ");
    }

    public static void main(String[] args) {
        new MergeSort().run();
    }
}


Related articles: