Jacob_Thomas

Merge sort

Jan 28th, 2021
449
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2. class mergesort
  3. {
  4.      public static void main(String args[])
  5.     {
  6.         Scanner sc = new Scanner(System.in);
  7.         System.out.println("Enter size");
  8.         int n = sc.nextInt();
  9.         int arr[] = new int[n];
  10.         System.out.println("Enter array");
  11.        
  12.         for(int x=0; x<n; x++)
  13.             arr[x] = sc.nextInt();
  14.  
  15.         System.out.println("\nGiven Array \n"+ Arrays.toString(arr));
  16.  
  17.         mergesort m = new mergesort();
  18.         m.sort(arr, 0, arr.length - 1);
  19.        
  20.         System.out.println("\nSorted Array \n"+ Arrays.toString(arr));
  21.  
  22.     }
  23.  
  24.     void mergefun(int arr[], int start, int mid, int end)
  25.     {
  26.         int n1 = mid - start + 1;
  27.         int n2 = end - mid;
  28.  
  29.         int L[] = new int[n1];
  30.         int R[] = new int[n2];
  31.  
  32.         for (int i = 0; i < n1; ++i)
  33.             L[i] = arr[start + i];
  34.         for (int j = 0; j < n2; ++j)
  35.             R[j] = arr[mid + 1 + j];
  36.         int i = 0, j = 0;
  37.         for(int x = start; x<=end; x++){
  38.             if(i < n1 && j < n2){
  39.                 if (L[i] <= R[j]){
  40.                     arr[x] = L[i];
  41.                     i++;
  42.                 }
  43.                 else {
  44.                     arr[x] = R[j];
  45.                     j++;
  46.                 }
  47.             }
  48.             else{
  49.                 if(i < n1){
  50.                     arr[x] = L[i];
  51.                     i++;
  52.                 }
  53.  
  54.                 if(j < n2){
  55.                     arr[x] = R[j];
  56.                     j++;
  57.                 }
  58.             }
  59.         }
  60.     }
  61.  
  62.     void sort(int arr[], int l, int r)
  63.     {
  64.         if (l < r) {
  65.             int m = (l + r) / 2;
  66.  
  67.             sort(arr, l, m);
  68.             sort(arr, m + 1, r);
  69.             mergefun(arr, l, m, r);
  70.         }
  71.     }
  72. }
  73.  
  74.  
RAW Paste Data