Multi-threaded Mergesort problems

Question

I'm trying to write a multi-threaded mergesort, and I'm having what to me are very confusing issues. I'm not fully aware of the rules of how threads share/use variables...

For example, if within a runnable class, I create another instance of that Runnable and pass it one of my arrays as a parameter, do edits that class makes transfer? It appears as if they do, but it also appears as if I'm having unexpected behavior.

Here is my code:

public class PSort implements Runnable {

private int [] Arr;
private int begin;
private int end;

public void run () {
    // Base Case - Insertion sort
    if(this.end-this.begin <= 10) {
        InsertionSort();
    }
    else {
        int left_start  = this.begin;
        int left_end    = this.begin + (this.end-this.begin)/2;
        int right_start = this.begin + (this.end-this.begin)/2 + 1;
        int right_end   = this.end;


        Thread t1 = new Thread(new PSort(this.Arr, left_start, left_end));
        Thread t2 = new Thread(new PSort(this.Arr, right_start, right_end));
        t1.start();
        t2.start();

        try {
            t1.join();
            t2.join();

            merge(left_start, left_end, right_start, right_end);
        } catch (Exception e) {}
    }
}

public PSort (int[] A, int begin, int end) {
    this.Arr = A;
    this.begin = begin;
    this.end = end;
    System.out.println("New thread: " + this.begin + " " + this.end);
}

public static void ParallelSort (int[] A, int begin, int end) {

    PSort psort = new PSort(A, begin, end);
    Thread thread = new Thread(psort);

    thread.start();

    try {
        thread.join();
        psort.printArray();
    } catch (InterruptedException e) {}
}

public void printArray() {
    int count = 0;
    for(int x = this.begin; x < this.end; x++) {
        if(count < 10) {
            System.out.print(Arr[x] + " ");
            count++;
        }
        else {
            count = 1;
            System.out.print("\n" + Arr[x] + " ");
        }
    }
}

private void InsertionSort () {
    for(int x = this.begin; x < this.end; x++) {
        int currentNum = this.Arr[x];
        int hole = x;
        while((hole > 0) && (this.Arr[hole-1] > currentNum)) {
            this.Arr[hole] = this.Arr[hole-1];
            hole = hole - 1;
        }
        this.Arr[hole] = currentNum;
    }
}

private void merge (int left_start, int left_end, int right_start, int right_end) {
    /*
    int length = right_end - left_start;

    int[] temp = new int[length];
    int leftP = left_start;
    int rightP = right_start;
    int index = 0;

    while((leftP <= left_end) && (rightP < right_end)) {
        if(Arr[leftP] < Arr[rightP]) {
            temp[index++] = Arr[leftP++];
        }
        else {
            temp[index++] = Arr[rightP++];
        }
    }   
    while(leftP <= left_end) {
        temp[index++] = Arr[leftP++];
    }
    while(rightP < right_end) {
        temp[index++] = Arr[rightP++];
    }

    System.arraycopy(temp, 0, Arr, left_start, length);
    */

}
}

Now, I am calling PSort.ParallelSort with a size-40 array filled with random integers 0-9, and this is the output I get:

New thread: 0 40
New thread: 0 20
New thread: 21 40
New thread: 0 10
New thread: 11 20
New thread: 21 30
New thread: 31 40
0 1 1 2 2 2 6 7 7 8 
8 3 3 3 4 4 5 5 6 7 
9 2 3 3 3 4 7 8 9 9 
2 2 6 7 7 7 8 8 9 9 

Notice that I have commented out the "merge" section of my routine, so I would expect each individual line of output to be correctly sorted, but that is not the case. I tested the InsertionSort by itself, and it doesn't seem to ever fail, so there seem to be some concurrency issues at work here which I'm completely ignoring.

Note: I realize there are some more serious problems at work here, because the higher numbers are weighted towards the last two rows of the overall array, even though I'm not merging...

Answer 1

The bug is in your InsertionSort method (which should be named starting with a lower-case letter, by the way):

int hole = x;
while ((hole > 0) && /* ... */) {
    // ...
    hole--;
}

So you're starting at x, which is within the assigned segment, but moving back to 0, so all the threads end up writing on the same segments. Yes, the data is shared between the threads, that's the difficulty when multi-threading.