Im trying to write kind of "Merge Sort" using threads in Java. Basically Monitor class gets an array and creates an Array Stack which contains arrays of length 1. Monitor has 3 functions synchronized:

• getSubArray - gets an subarray from stack, if the stack is empty it just waits.
• setSubArray - push an subarray to stack, and notify all threads.
• canContinue - check if the if we finished sorting the array.

Monitor Class:

public class MergeSort {
    
    private Stack<int[]> subArrays;
    private int arraySize;
    

    public MergeSort(int[] array)
    {
        
        this.subArrays = new Stack<int[]>();
        this.arraySize = array.length;
        for (int i = 0; i < array.length; i++) {
            int[] temp = new int[1];
            temp[0] = array[i];
            this.subArrays.push(temp);
        }
    }
    
    
    public synchronized void setSubArray(int[] newSubArray,String threadName)
    {
        this.subArrays.push(newSubArray);
        System.out.println(threadName+ " pushing new array to Stack, and notifying all threads");
        notifyAll();
    }
    
    
    public synchronized boolean canContinue() {
        if(this.subArrays.peek()==null)
            try {
                wait();
            } catch(InterruptedException e) {
                e.printStackTrace();
            }
        return this.subArrays.peek() != null && this.subArrays.peek().length < arraySize;
    }
    
    public synchronized int[] getSubArray(String threadName)
    {
        while(this.subArrays.isEmpty()) {
            try {
                System.out.println(threadName+ ": subarrays is empty.... going to wait");
                wait();
                System.out.println(threadName+ ": i got notified, continuing getting a subarray");
            }
        catch (InterruptedException e) {
            e.printStackTrace();
            }
        }
        return subArrays.pop();
    }
}

Thread Class

public class Sorter extends Thread {
    
    private MergeSort arrayToSort;
    private String threadName;
    private int[] subArray1;
    private int[] subArray2;
    
    public Sorter(MergeSort arrayToSort,String name)
    {
        this.arrayToSort=arrayToSort;
        this.threadName = name;
    }
    
    public void run() {
        super.run();
                
        while(this.arrayToSort.canContinue())
        {
            this.subArray1 = this.arrayToSort.getSubArray(this.threadName);
            System.out.println(this.threadName+": subArray1 was set successfully");
            
            this.subArray2 = this.arrayToSort.getSubArray(this.threadName);
            System.out.println(this.threadName+": Got two sub arrays:\n"+ "\tSubArray1: "+ Arrays.toString(subArray1)+ 
                                "\n\tSubArray2: "+ Arrays.toString(subArray2));
            
            int[] subSortedArray=mergeSubArraySorted(this.subArray1,this.subArray2);
            
            System.out.println(this.threadName+ ": Merged two sub arrays: "+ Arrays.toString(subSortedArray));
            
            this.arrayToSort.setSubArray(subSortedArray,this.threadName);
        }
        
        System.out.println(this.threadName+": Oh wow, we finished sorting the array :D");
    }
    
    public int[] mergeSubArraySorted(int[] subArray1, int[] subArray2)
    {
        int subArraySortedLength = subArray1.length +subArray2.length;
        int[] subArraySorted = new int[subArraySortedLength];
        for (int i = 0; i < subArraySorted.length; i++) {
            if(i < subArray1.length){
                subArraySorted[i] = subArray1[i];
            }
            else{
                subArraySorted[i] = subArray2[i - subArray1.length];
            }
        }
        Arrays.sort(subArraySorted);
        return subArraySorted;
    }

}

Main

public class Main {

    public static void main(String[] args) {
        int[] arrayToSort = {4,5,1};
        
        MergeSort merge = new MergeSort(arrayToSort);
        Sorter sort1 = new Sorter(merge,"sort1");
        Sorter sort2 = new Sorter(merge,"sort2");
        
        sort1.start();
        sort2.start();      
    }
}

The issue I see is that while 2 threads are running, thread1 is waiting in getSubArray and while thread2 is doing his work and then push the sorted. thread2 goes to getSubArray and "steal" the array from thread1. As you see in (row5) Sort1 is in getSubArray and waiting for Sort2 to push to Stack.(row6,7) Sort2 push to stack but it continues and goes to GetSubArray which is synchronized .

the output:

 1. sort2: subArray1 was set successfully
 2. sort2: Got two sub arrays:
    SubArray1: [5]
    SubArray2: [4]
 3. sort1: subArray1 was set successfully
 4. sort2: Merged two sub arrays: [4, 5]
 5. sort1: subarrays is empty.... going to wait
 6. sort2 pushing new array to Stack, and notifying all threads
 7. sort2: subArray1 was set successfully
 8. sort1: i got notified, continuing getting a subarray
 9. sort1: subarrays is empty.... going to wait
 10. sort2: subarrays is empty.... going to wait