Guest User

Untitled

a guest
Oct 21st, 2019
101
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