ulvis.paste.net

Paste Search Dynamic
Recent pastes
MergeSort
  1. /* package whatever; // don't place package name! */
  2. import java.util.*;
  3. import java.lang.*;
  4. import java.io.*;
  5.  
  6. /* Name of the class has to be "Main" only if the class is public. */
  7. class Main
  8. {
  9.         static class MergeSort {
  10.                 public static void mergeSort(int[] arr, int n) {
  11.                         if (n < 2) return;
  12.                        
  13.                         int mid = n / 2;
  14.                         int[] left = new int[mid];
  15.                         int[] right = new int[n - mid];
  16.                        
  17.                         for (int i = 0; i < mid; i++) {
  18.                                 left[i] = arr[i];
  19.                         }
  20.                        
  21.                         for (int i = mid; i < n - mid; i++) {
  22.                                 right[i - mid] = arr[i];
  23.                         }
  24.                        
  25.                         mergeSort(left, mid);
  26.                         mergeSort(right, n - mid);
  27.                        
  28.                         merge(arr, left, right, mid, n - mid);
  29.                 }
  30.                
  31.                 public static void merge(int[] arr, int[] left, int[] right, int lSize, int rSize) {
  32.                         int i = 0, j = 0, k = 0;
  33.                        
  34.                         while (i < lSize && j < rSize) {
  35.                                 if (left[i] <= right[j]) {
  36.                                         arr[k++] = left[i++];
  37.                                 } else {
  38.                                         arr[k++] = right[j++];
  39.                                 }
  40.                         }
  41.                        
  42.                         while (i < lSize) {
  43.                                 arr[k++] = left[i++];
  44.                         }
  45.                        
  46.                         while (j < rSize) {
  47.                                 arr[k++] = right[j++];
  48.                         }
  49.                 }
  50.         }
  51.         public static void main (string[] args) throws java.lang.exception
  52.         {
  53.                 // your code goes here
  54.                 int[] arr = new int[] {1,5,2,10,6,8,5,2,20};
  55.                 for (int i = 0; i < arr.length; i++) {
  56.                         system.out.println(arr[i]);
  57.                 }
  58.                
  59.                 system.out.println();
  60.                 system.out.println();
  61.                
  62.                 MergeSort.mergeSort(arr, arr.length);
  63.                
  64.                 for (int i = 0; i < arr.length; i++) {
  65.                         system.out.println(arr[i]);
  66.                 }
  67.         }
  68. }
Parsed in 0.020 seconds