SHARE
TWEET

Untitled

a guest Jun 19th, 2017 47 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package RandomizedSelect;
  2.  
  3. import java.util.LinkedList;
  4.  
  5. public class ParallelMergeSort {
  6.     static void mergeSort(int[] A){
  7.         mergeSort(A, 0, A.length-1);
  8.     }
  9.     static void mergeSort(int[] A, int low, int high){
  10.         if(high - low < 1){
  11.             return;
  12.         }else{
  13.             int pivot = Math.floorDiv(high + low, 2);
  14.             Thread proc = new Thread(new Runnable(){
  15.                 @Override
  16.                 public void run(){
  17.                     mergeSort(A, low, pivot);
  18.                     mergeSort(A, pivot + 1, high);
  19.                 }
  20.             });
  21.             proc.start();
  22.             while(proc.isAlive());
  23.             merge(A, low, pivot, pivot+1, high);
  24.         }
  25.     }
  26.     static void merge(int[] a, int l1, int r1, int l2, int r2) {
  27.         LinkedList<Integer> list = new LinkedList<Integer>();
  28.         for(int i = l1; i <= r1; i++){
  29.             list.add(a[i]);
  30.         }
  31.         int index = 0;
  32.         for(int i = l2; i <= r2; i++){
  33.             while(index < list.size() && list.get(index) < a[i]) index++;
  34.             list.add(index, a[i]);
  35.         }
  36.         for(int i = 0; i < list.size(); i++){
  37.             a[i + l1] = list.get(i);
  38.         }
  39.     }
  40.     public static void main(String[] args){
  41.         int[] array = {1,5,12,15,12,11,3, 16, 2, 5, 18};
  42.         mergeSort(array);
  43.         for(int i: array){
  44.             System.out.print(i + " ");
  45.         }
  46.     }
  47. }
RAW Paste Data
Top