Одновременное слияние многих отсортированных массивов

В настоящее время я работаю над программой для одновременной сортировки строк. Моя программа принимает файл, считывает каждую строку файла в массив и разбивает массив строк на более мелкие массивы строк. Затем программа запускает по одному потоку для каждого из меньших массивов и выполняет их быструю сортировку. Как только каждый поток закончил сортировку своего массива, основной поток собирает все результаты из объектов потока. Затем предполагается объединить меньшие, теперь отсортированные массивы в один большой отсортированный массив.

В настоящее время я решил это, используя однопоточную сортировку слиянием, чтобы объединить отсортированные массивы, возвращаемые потоками быстрой сортировки. Теперь проблема с этим, поскольку слияние не происходит одновременно, сортировка в файле с использованием небольшого количества потоков (1-4) фактически делает сортировку программы максимально быстрой. Если я немного увеличу количество потоков (скажем, 15 потоков), программа на самом деле будет работать немного медленнее, чем при меньшем количестве потоков. Чтобы решить эту проблему, я хочу ввести параллелизм в мою сортировку/вложение массива слиянием.

Что я хочу сделать, так это: как только два потока закончат быструю сортировку своих частей в файле, новый поток будет вкладывать эти две части вместе, пока каждая часть в файле не будет отсортирована.

Мы очень ценим любую помощь, и я благодарен за пример кода и/или псевдокода. Заранее спасибо! :)

Текущий код для сортировки массива:

public synchronized String[] sort(){
    String[] sortedWords = new String[words.length];
    SortingThread[] sts = new SortingThread[threads];

    for(int i = 0; i < threads; i++){
        sts[i] = new SortingThread(this, splitWords[i]);
    }

    for(SortingThread st : sts){
        st.start();
    }

    for(SortingThread st : sts){
        try {
            st.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    indexes = new int[sts.length];

    for(int i = 0; i < indexes.length; i++){
        indexes[i] = 0;
    }


//This is where my merge-sorting currently starts.

    ArrayList<String> toAddTo = new ArrayList<String>();

    while(!allIndexesHaveBeenRead(sts)){
        String globalMinimum = null;
        int globalMinThread = -1;
        currentIteration: for (int i = 0; i < sts.length; i++) {
            String current;
            try{
                current = sts[i].sorted[indexes[i]];
            } catch(Exception e){
                continue currentIteration;
            }
            try{
                if(globalMinimum == null){
                    globalMinimum = current;
                    globalMinThread = i;
                }
                else if(current.compareTo(globalMinimum) < 0){
                    globalMinimum = current;
                    globalMinThread = i;
                }
            } catch (NullPointerException e){
                continue;
            }
        }
        toAddTo.add(globalMinimum);
        indexes[globalMinThread]++;
    }

    sortedWords = toAddTo.toArray(sortedWords);

    int len = 0;
    for (int i = 0; i < sortedWords.length; i++) {
        if(sortedWords[i] != null){
            len++;
        }
    }

    String[] toReturn = new String[len];

    for (int i = 0; i < toReturn.length; i++) {
        toReturn[i] = sortedWords[i];
    }

    return toReturn;
}