SHARE
TWEET

Untitled

a guest Oct 21st, 2019 93 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package com.company;
  2. import java.util.ArrayList;
  3.  
  4. public class Main {
  5.  
  6.     public static void main(String[] args) {
  7.         ArrayList<Integer> a = new ArrayList<>();
  8.         int[] stuff = {38, 27, 43, 3, 9, 82, 10};
  9.         for (int i: stuff) { a.add(i); }
  10.         mergeSort(a, 0, a.size()-1);
  11.  
  12.         printArray(a);
  13.     }
  14.  
  15.     private static void printArray(ArrayList<Integer> a) {
  16.         StringBuilder sb = new StringBuilder();
  17.         for (int i : a) {
  18.             sb.append(i);
  19.             sb.append(", ");
  20.         }
  21.         sb.delete(sb.length()-2, sb.length());
  22.         System.out.println(sb);
  23.     }
  24.  
  25.     public static void mergeSort(ArrayList<Integer> array, int leftIndex, int rightIndex) {
  26.         if (rightIndex > leftIndex) {
  27.             int middleIndex = (rightIndex + leftIndex) / 2;
  28.             mergeSort(array, leftIndex, middleIndex);
  29.             mergeSort(array, middleIndex + 1, rightIndex);
  30.             merge(array, leftIndex, middleIndex, rightIndex);
  31.         }
  32.     }
  33.  
  34.     private static void merge(ArrayList<Integer> array, int leftIndex, int middleIndex, int rightIndex) {
  35.         // first subarraylist should be array[leftIndex..middleIndex]
  36.         ArrayList<Integer> leftList = new ArrayList<>();
  37.         for (int i = leftIndex; i <= middleIndex; i++) {
  38.             leftList.add(array.get(i));
  39.         }
  40.  
  41.         // second subarraylist should be array[middleIndex+1..rightIndex]
  42.         ArrayList<Integer> rightList = new ArrayList<>();
  43.         for (int i = middleIndex + 1; i <= rightIndex; i++) {
  44.             rightList.add(array.get(i));
  45.         }
  46.  
  47.         int i = leftIndex;
  48.         int j = 0;
  49.         int k = 0;
  50.  
  51.         while (j < leftList.size() && k < rightList.size()) {
  52.             if (leftList.get(j) < rightList.get(k)) {
  53.                 array.set(i, leftList.get(j));
  54.                 j++;
  55.             } else {
  56.                 array.set(i, rightList.get(k));
  57.                 k++;
  58.             }
  59.             i++;
  60.         }
  61.         while (leftList.size() > j) {
  62.             array.set(i, leftList.get(j));
  63.             i++;
  64.             j++;
  65.         }
  66.         while (rightList.size() > k) {
  67.             array.set(i, rightList.get(k));
  68.             i++;
  69.             k++;
  70.         }
  71.     }
  72. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top