Multi thread array sort Java

Question

So hello!

I'm trying to sort int array with several threads. Now I've got something like this:

import java.util.Arrays;


public class MultiTread extends  Thread{

int sizeOfArray;
public static int treadsN = 4;
public  static  int sortFrom;
public  static  int sortTo;

public MultiTread(int sizeOfArray, int treadsN) {
    this.sizeOfArray = sizeOfArray;
    this.treadsN = treadsN;
}

public MultiTread(int[] arrayToSort, int sizeOfArray) {
    this.sizeOfArray = sizeOfArray;
}



public static int [] creatingArray(int sizeOfArray) {
    int [] arrayToSort = new int[sizeOfArray];
    int arrayLength = arrayToSort.length;
    for (int counter = 0; counter<arrayLength; counter++){
        arrayToSort[counter] = (int)(8000000*Math.random());
    }
    return arrayToSort;
}

public  static  int [] sortInSeveralTreads(final int [] arrayToSort){
    int [] newArr = new int[arrayToSort.length];
    int numberOfThreads = treadsN;
    if (numberOfThreads == 0){
        System.out.println("Incorrect value");
        return arrayToSort;
    }
    if (numberOfThreads == 1){
        Arrays.sort(arrayToSort);
        System.out.println("Array sorted in 1 thread");
    } else {
         final int lengthOfSmallArray = arrayToSort.length/numberOfThreads;
        sortFrom = 0;
        sortTo = lengthOfSmallArray;
        for (int progress = 0; progress < numberOfThreads; progress++){
            final int [] tempArr = Arrays.copyOfRange(arrayToSort,sortFrom,sortTo);
            new Thread(){public void run() {
                Arrays.sort(tempArr);
            }}.start();
            sortFrom = sortTo;
            sortTo += lengthOfSmallArray;
            newArr =  mergeSort(newArr, tempArr);
        }
        new Thread(){public void run() {
            Arrays.sort(Arrays.copyOfRange(arrayToSort, arrayToSort.length-lengthOfSmallArray, arrayToSort.length));
        }}.start();
        newArr = mergeSort(newArr, arrayToSort);
    }
    return newArr;
}

public static  int [] mergeSort(int [] arrayFirst, int [] arraySecond){
    int [] outputArray = new  int[arrayFirst.length+arraySecond.length];
    while (arrayFirst.length != 0 && arraySecond.length != 0){
        int counter = 0;
        if (arrayFirst[0] < arraySecond[0]){
            outputArray[counter] = arrayFirst[0];
            counter++;
            arrayFirst = Arrays.copyOfRange(arrayFirst, 1, arrayFirst.length);
        }else {
            outputArray[counter] = arraySecond[0];
            counter++;
            arraySecond = Arrays.copyOfRange(arraySecond, 1, arraySecond.length);
        }
    }
    return outputArray;
}


public static void main(String[] args){
    long startTime;
    long endTime;
    int [] a = creatingArray(8000000);
    startTime = System.currentTimeMillis();
    a =  sortInSeveralTreads(a);
    endTime = System.currentTimeMillis();
    System.out.println(Thread.activeCount());
    System.out.printf("Sorted by: %d treads in %.7f seconds %n", treadsN, (float)(endTime-startTime)*1e-6);
    try {
        Thread.currentThread().sleep(1000);
    } catch (InterruptedException e) {
        e.printStackTrace();
    }
    System.out.println(Thread.activeCount());
}
}

I know that it's not very good realization. All works fine but merge sort works too bad - it crashes... Error should be in that lines:

Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
at java.util.Arrays.copyOfRange(Arrays.java:3137)
at MultiTread.mergeSort(MultiTread.java:78)
at MultiTread.sortInSeveralTreads(MultiTread.java:61)
at MultiTread.main(MultiTread.java:94)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
at java.lang.reflect.Method.invoke(Method.java:597)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:120)

What i'm doing wrong?

Answer 1

Okay there are several issues:

First your array size is way too large. Which is why you are running out of Memory (8000000) should be tried with a low number say 1000. Even with that your code will probably crash elsewhere as it stands.

Second your code makes very little sense as it stands you are mixing static and non static calls ... e.g. Thread.currentThread().sleep(1000) is bizarre, you are not in the current Thread.

The thread creation where you perform Array.sort.

I suggest that first you create a simple multi-threaded program before dealing with sorting job. Also recommend that you implement Runnable interface rather than extending the Thread class to create your worker class.

Answer 2

while (arrayFirst.length != 0 && arraySecond.length != 0){

here it goes in infinite loop once the conditions are satisfied and hence the memory heap is getting OutOfMemoryError

It is not at all terminated so You should include some code to terminate this loop.

Answer 3

Well, you're running out of the memory allowed by use by the J.V.M..

I've not checked to see that your algorithm is correct, but you should try the code with a much smaller array to see if it works alright, say, 1000.

You make several copies of the array (or at least partial copies) throughout your program, in threads. Each thread then is allocating a large amount of data. For this reason, you may wish to reconsider your design, or you will continue to run into this problem. If you find no way to reduce this allocation and my next paragraph does not help you, then you may need to resort to the use of files to sort these large arrays, instead of attempting to hold everything in memory at once.

You can increase the heap size by following instructions on this page (first link I found, but it has the right information): http://viralpatel.net/blogs/2009/01/jvm-java-increase-heap-size-setting-heap-size-jvm-heap.html This will allow you to hold allocate more memory from your Java program.