Merge Sort

This is a simple implementation of Merge Sort in java.
Though this is not the most efficient one, but still this can be considered as one version of implementation. I will post as and when I make improvements.


public class MergeSort {
    public static void main(String...args) {
        int a[]={3,2,5,1,3,2,7,8,6,4,0,7,9};
        System.out.println("len:"+a.length);
        MergeSort m = new MergeSort();
        int p = 0;
        int r = a.length;
        m.mergeSort(p,r-1,a);
        System.out.println("output:");
        for(int n=0; n< a.length;n++) {
            System.out.print(a[n]);
        }
    }
   
    public void mergeSort(int p, int r,int...a1) {
        if (p < r) {
            int q = (int) Math.floor((p+r)/2);
            mergeSort(p,q,a1);
            mergeSort(q+1,r,a1);
            merge(p,q,r,a1);
        }
    }
   
    public void merge(int p, int q, int r, int...a1) {
      int n1 = q-p+1;
      int n2= r-q;
         
      int[] a2= new int[n1];
      int[] a3= new int[n2];
     
      for(int i=0;i<n1;i++) {
          a2[i]=a1[p+i];
      }
     
      for(int i=0;i<n2;i++) {
          a3[i]= a1[q+i+1];
      }
     
      int k=0,l=0;
      int o;
      for(o=p;o<=r;o++) {
          if((k==n1) || (l==n2)){
              break;
          }
        if(a2[k] < a3[l]) {
          a1[o]=a2[k];
          k++;
        } else {
            a1[o] = a3[l];
            l++;
        }
      }
     
      if(k<n1){
          while(k<n1) {
              a1[o]=a2[k++];
              o++;
          }
      } else if(l<n2) {
          while(l<n2) {
              a1[o]=a3[l++];
              o++;
          }
      }
    }
}

Insertion Sort in Java


This is a simple implementation of insertion sort in java which can be useful for reference purpose. It takes an array as input, sort that array using insertion sort logic and prints the output.

public class InsertionSort {

    public static void main(String...args) {
        int[] a={1,5,2,9,8,3,4,5};
        int key,i;
        for(int j=1; j< a.length;j++) {
          key = a[j];
          i=j-1;
          while(i>=0 && a[i] > key) {
              a[i+1]=a[i];
              i=i-1;
          }
          a[i+1]=key;
        }
       
        for(int a1:a) {
          System.out.println(a1);
        }
    }
}
 

test