2

I'm trying to implement multi-threading using merge sort. I have it making new threads at the point where it cuts an array in half.
The array is sorted depending on the: [size of the array] vs [how many times I create new threads] For instance: the array will be sorted if I let it create merely two threads on an array of size 70, but if I let it create 6, it will come back unsorted. One thing I thought it might be is that the threads weren't sync'd, but I used threadName.join()

here is some code: merge.java

import java.util.Random;

public class merge implements Runnable {
    int[] list;
    int length;
    int countdown;

    public merge(int size, int[] newList, int numberOfThreadReps, int firstMerge) {
        length = size;
        countdown = numberOfThreadReps;
        list = newList;
        if (firstMerge == 1)
            threadMerge(0, length - 1);
    }

    public void run() {
        threadMerge(0, length - 1);
    }

    public void printList(int[] list, int size) {
        for (int i = 0; i < size; i++) {
            System.out.println(list[i]);
        }
    }

    public void regMerge(int low, int high) {
        if (low < high) {
            int middle = (low + high) / 2;
            regMerge(low, middle);
            regMerge(middle + 1, high);
            mergeJoin(low, middle, high);
        }
    }

    public void mergeJoin(int low, int middle, int high) {
        int[] helper = new int[length];

        for (int i = low; i <= high; i++) {
            helper[i] = list[i];
        }

        int i = low;
        int j = middle + 1;
        int k = low;

        while (i <= middle && j <= high) {
            if (helper[i] <= helper[j]) {
                list[k] = helper[i];
                i++;
            } else {
                list[k] = helper[j];
                j++;
            }
            k++;
        }
        while (i <= middle) {
            list[k] = helper[i];
            k++;
            i++;
        }
        helper = null;
    }

    public void threadMerge(int low, int high) {
        if (countdown > 0) {
            if (low < high) {
                countdown--;
                int middle = (low + high) / 2;
                int[] first = new int[length / 2];
                int[] last = new int[length / 2 + ((length % 2 == 1) ? 1 : 0)];
                for (int i = 0; i < length / 2; i++)
                    first[i] = list[i];
                for (int i = 0; i < length / 2 + ((length % 2 == 1) ? 1 : 0); i++)
                    last[i] = list[i + length / 2];

                merge thread1 = new merge(length / 2, first, countdown, 0);// 0
                                                                            // is
                                                                            // so
                                                                            // that
                                                                            // it
                                                                            // doesn't
                                                                            // call
                                                                            // threadMerge
                                                                            // twice
                merge thread2 = new merge(length / 2
                        + ((length % 2 == 1) ? 1 : 0), last, countdown, 0);

                Thread merge1 = new Thread(thread1);
                Thread merge2 = new Thread(thread2);
                merge1.start();
                merge2.start();

                try {
                    merge1.join();
                    merge2.join();
                } catch (InterruptedException ex) {
                    System.out.println("ERROR");
                }

                for (int i = 0; i < length / 2; i++)
                    list[i] = thread1.list[i];
                for (int i = 0; i < length / 2 + ((length % 2 == 1) ? 1 : 0); i++)
                    list[i + length / 2] = thread2.list[i];

                mergeJoin(low, middle, high);
            } else {
                System.out.println("elsd)");
            }
        } else {
            regMerge(low, high);
        }
    }
}

proj4.java

import java.util.Random;

public class proj4 {
    public static void main(String[] args) {
        int size = 70000;
        int threadRepeat = 6;
        int[] list = new int[size];
        list = fillList(list, size);
        list = perm(list, size);
        merge mergy = new merge(size, list, threadRepeat, 1);
        // mergy.printList(mergy.list,mergy.length);
        for (int i = 0; i < mergy.length; i++) {
            if (mergy.list[i] != i) {
                System.out.println("error)");
            }
        }
    }

    public static int[] fillList(int[] list, int size) {
        for (int i = 0; i < size; i++)
            list[i] = i;
        return list;
    }

    public static int[] perm(int[] list, int size) {
        Random generator = new Random();
        int rand = generator.nextInt(size);
        int temp;
        for (int i = 0; i < size; i++) {
            rand = generator.nextInt(size);
            temp = list[i];
            list[i] = list[rand];
            list[rand] = temp;
        }
        return list;
    }

}

so TL;DR my array isn't getting sorted by a multithreaded merge sort based on the size of the array and the number of times I split the array by using threads...why is that?

1 Answer 1

5

Wow. This was an interesting exercise in masochism. I'm sure you've moved on but I thought for posterity...

The bug in the code is in mergeJoin with the middle argument. This is fine for regMerge but in threadMerge the middle passed in is (low + high) / 2 instead of (length / 2) - 1. Since in threadMerge low is always 0 and high is length - 1 and the first array has (length / 2) size. This means that for lists with an odd number of entries, it will often fail depending on randomization.

There are also a number of style issues which makes this program significantly more complicated and error prone:

  • The code passes around a size of the arrays when Java has a convenient list.length call which would be more straightforward and safer.
  • The code duplicates calculations (see length/2) in a number of places.
  • The code should be able to sort inside the array without creating sub-arrays.
  • Classes should start with an uppercase letter (Merge instead of merge)
  • firstMerge should be a boolean
  • The code names the Thread variable merge1 and the merge variable thread1. Gulp.
  • The merge constructor calling threadMerge(0,length -1) is strange. I would just put that call after the new call back in proj4. Then firstMerge can be removed.
  • I would consider switching to having high be one past the maximum value instead of the maximum. We tend to think like for (int i = 0; i < 10; i++) more than i <= 9. Then the code can have j go from low to < middle and k from middle to < high. Better symmetry.

Best of luck.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.