Многопоточная сортировка слиянием. java

Задание: написать многопоточную сортировку слиянием, на вход подаётся массив и число потоков.

Код работает только иногда и только для небольших массивов. (код должен работать для любых объектов, поэтому используется Comparable, но не суть). Так же, для нескольких потоков код работает примерно в 200 раз медленнее, чем для сортировки одним потоком(в задании необходимо привести пример, когда многопоточная сортировка слиянием работает быстрее, чем обычная). Проблема заключается в следующем: сортирует массив неправильно. Например: возьмём массив из 10 элементов и как-нибудь рандомно его заполним. В 90% случаев в ответ будет выведен правильный отсортированный массив по возрастанию. Однако, если, например, взять массив из 20 элементов, то уже всё, практически всегда будет выведен неправильный ответ, т.е. числа будут в неправильном, рандомном порядке. Исключений и ошибок вроде не кидает(по-крайней мере на тех тестах, на которых я проверяла), только ответ в большинстве случаев неверный, выводится неотсортированный массив Помогите, пожалуйста, найти проблему и решение этой проблемы. Так же было бы очень неплохо, если бы вы подсказали сам алгоритм решения моей задачи, какие структуры использовать и т.д.

public class Sort {
Comparable []a; // сортируемый массив
Threds []threads; //массив потоков
int N = 0; //количество потоков(задаётся на входе)
int threadNum = 0;//номер потока, который используем в данный момент(индекс в массиве threads)
int left = 0, right = 0; //левая и правая граница сортируемой части массива
public class Threds extends Thread { //класс для инициализации потоков
    int l;
    int r;
    public Threds(int left, int rigth) {
        l = left;
        r = rigth;
    }
    public void run() { MergeSort(l, r, threadNum); } //вызываем рекурсивно мёрдж-сорт
}
public Sort (int NumberOfThreads, Comparable []array) {
    N = NumberOfThreads;
    threads = new Threds[N];
    a = array;
}
void MergeSort(int l, int r, int tNum) {
    if(l >= r) //если левая граница больше либо равно  правой, то ничего не нужно сортировать, т.к. подмассив состоит из 1 элемента
        return;
    int mid = (l + r) / 2; //вычисляем середину подмассива
    if(N == 1){ //если число потоков равно 1, то обычная сортировка, которая кстати у меня работает
        MergeSort(l, mid, 0);
        MergeSort(mid + 1, r, 0);
    }
    else {
        if(tNum > N) // проверка, чтобы не выйти за границы массива(другими словами, вычисляем индекс потока в масcиве threads по модулю N)
            tNum = N - tNum;
        int m = tNum, n = tNum + 1;
       // Threds t1 = new Threds(l,mid); //вариант, когда не нужно использовать дополнительный массив потоков, но как тогда контролировать используемое колличество потоков?
       // t1.start();
        threads[m] = new Threds(l, mid);
        threads[m].start(); //запускаем сортировку от левой части подмассива
        left = mid + 1;
        right = r;
        threads[n] = new Threds(mid + 1, r);
        threads[n].start();// запускаем сортировку от правой части подмассива
       // Threds t2 = new Threds(mid+1, r);
       // t2.start();
        try { //ждём, чтобы оба потока завершились, чтобы затем слить 2 части подмассива(левую и правую)
            threads[m].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        try {
            threads[n].join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    mearge(a, l, mid, r); // сливаем
}
void mearge(Comparable []array, int l, int mid, int r){ //обычный алгоритм слияния
    Comparable []buf = new Comparable[array.length];
    Comparable []res = new Comparable[array.length]; //заводим промежуточный массив для перестраховки(например один поток не завершил работу, а другой пытается обратиться к array, записать в него что-то или считать)
    synchronized (array){
        for(int i = 0; i < array.length; i++){
            buf[i] = array[i];
            res[i] = array[i];
        }
    }
    int i = l, j = mid + 1;
    for (int k = l; k <= r; k++) {
        if (i > mid) {
            res[k] = buf[j];
            j++;
        } else if (j > r) {
            res[k] = buf[i];
            i++;
        } else if (buf[j].compareTo(buf[i]) > 0) {
            res[k] = buf[i];
            i++;
        } else {
            res[k] = buf[j];
            j++;
        }
    }
    synchronized (array){
        for(int t = 0; t < array.length; t++) {
            array[t] = res[t];
        }
    }
}

}