sortierte Arrayteile zusammenfügen

[El Hadji]

Servus Community,
So eine aller letzte Frage. Kurze Problemstellung habe eine unsortierte Array und soll sie in 4 ungefähr gleich große Arrays teilen und diese parallel sortieren und danach zusammenfügen. Parallel sortieren klappt super nur das zusammenfügen ist das Problem.

Die vorgebene Klasse MergeSort, hilft mir auch nicht wirklich weiter hier die vorgegebene:

package parsort.geg;


public class MergeSort {
   
    private int[] b = new int[0];
   
    /*
     * Sortiert das Teil-Array a[start,...,ende-1] aufsteigend.
     */
    public void sort(int[] a, int start, int ende) {
        if(ende - start > 1) {
            int m = (start+ende)/2;   // start < m < ende
            sort(a,start,m);
            sort(a,m,ende);
            merge(a,start,m,ende);
        }
       
    }

    /*
     * Voraussetzung: a[start,...,m-1] und a[m,...,ende-1] sind sortiert.
     * Ergebnis: Die Elemente in a[start,...,ende-1] sind so umgeordnet,
     *           dass sie aufsteigend sortiert sind.
     */
    public final void merge(int[] a, int start, int m, int ende) {
        if(b.length < a.length) {
            b = new int[a.length];
        }
        merge(a,b,start,m,ende);
    }

    private void merge(int[] a, int[] b, int start, int m, int ende) {
        int i=start;
        int j=m;
        for(int k=start; k<ende; k++) {
            if(i < m && (j >= ende || a[i] < a[j])) {
                b[k] = a[i];
                i++;
            } else {
                b[k] = a[j];
                j++;
            }
        }
        for(int k=start; k<ende; k++) a[k] = b[k];
    }
   
   
}

Dann hab ich natürlich eine Unterklasse von Thread geschrieben:

package parsort;

import java.util.*;

public class SortThread extends Thread
{
   private int [] a;
   private int [] b;
   private int start;
   private int ende;
   private String s;
  
    public SortThread(int [] a, int start, int ende, String s)
    {
        this.s = s;
        this.a = a;
        b = new int[ende-start];
        for(int i = 0; i < b.length; i++)
        {
            b[i] = a[start];
            start++;
        }
     
     
    }
   
   
   
    public int [] sort()
    {
       Arrays.sort(b);
       return b;
      
       /*
       for(int i = 0; i < b.length; i++)
       {
           System.out.println(b[i]+ " " + s);
        }
        */
    }

  
    public void run()
    {
       sort();
    }
}

und meine eigene ParallelSortklasse die bis aufs merge stimmt, leider komm ich da nicht weiter:

package parsort;

import parsort.geg.MergeSort;
import java.util.*;


public class ParallelMergeSort extends MergeSort
{
    // instance variables - replace the example below with your own
    private int x;

    /**
     * Constructor for objects of class ParallelMergeSort
     */
    public ParallelMergeSort()
    {
      
    }

   
    public void sort(int [] a)
    {
        if(a.length >= 4)
        {
        int b = a.length/4;
       
        SortThread thread1 = new SortThread(a,0,b, " 1ster");
        SortThread thread2 = new SortThread(a,b,b*2, " 2ter");
        SortThread thread3 = new SortThread(a,b*2,b*3, " 3ter");
        SortThread thread4 = new SortThread(a,(b*3),a.length, " 4ter");
     
     
      thread1.start();
      thread2.start();
      thread3.start();
      thread4.start();
     
      try {
          thread1.join();
          thread2.join();
          thread3.join();
          thread4.join();
       
          } catch (InterruptedException e) {
            throw new RuntimeException(e);
        }
       
        merge(a,thread1.sort(),thread2.sort(),thread3.sort(),thread4.sort());
}
     
     else Arrays.sort(a);
  
       
     
    }
   
    void merge(int[] a, int[] b1, int[] b2, int [] b3, int [] b4)
    {
        int i1 = 0;
        int i2 = 0;
        for(int i=0; i<a.length; i++) {
            if(i2 == b2.length || i1 < b1.length && b1[i1] < b2[i2]) {
                a[i] = b1[i1];
                i1++;
            } else {
                a[i] = b2[i2];
                i2++;
            }
        }
    }
}

Sorry für den ewig langen Tex, aber es ist definitv mein letzter Post, vielleicht beruhigt das ;-)
mfg El Hadji