Сортировка большого массива методом Merge Sort в один и несколько потоков с замерами времени

MultiMerger.java

package ua.rumata.sorters;


public class MultiMerger extends Thread {

    private int[] unsorted, sorted;

    // Ограничиваем максимальное количество запускаемых потоков
    private static final int MAX_THREADS = 8;


    public MultiMerger(int[] unsorted) {
        this.unsorted = unsorted;
    }

    public void run() {
        int middle;
        int[] left, right;

        if ( unsorted.length <= 1 ) {
            // Массив из 1 элемента точно отсортирован :)
            sorted = unsorted;
        } else {

            // Иначе делим массив на левую и правую части
            middle = unsorted.length / 2;

            left = new int[middle];
            right = new int[unsorted.length - middle];

            System.arraycopy( unsorted, 0, left, 0, middle );
            System.arraycopy( unsorted, middle, right, 0, unsorted.length - middle );

            // Пока не превысили максимальное количество потоков, запускаем рекурсивно новые потоки на 2-х
            // новых массивах
            if ( activeCount() < MAX_THREADS ) {
                MultiMerger leftSort = new MultiMerger( left );
                MultiMerger rightSort = new MultiMerger( right );

                leftSort.start();
                rightSort.start();

                // Лепим докучи, как только потоки дождутся друг друга
                try {
                    leftSort.join();
                    rightSort.join();

                    sorted = SimpleMerger.merge( leftSort.getSorted(), rightSort.getSorted() );
                } catch ( Exception e ) {

                }

            } else {  // Тут уже новых потоков запускать нельзя - запускаем простой синглтредед алгоритм
                SimpleMerger leftSort = new SimpleMerger( left );
                SimpleMerger rightSort = new SimpleMerger( right );

                leftSort.sort();
                rightSort.sort();

                sorted = SimpleMerger.merge( leftSort.getSorted(), rightSort.getSorted() );
            }

        }
    }

    public int[] getSorted() {
        return sorted;
    }
}

SimpleMerger.java

package ua.rumata.sorters;

/**
 * Класс реализует сортировку массива методом Merge Sort
 * (см. http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D1%81%D0%BB%D0%B8%D1%8F%D0%BD%D0%B8%D0%B5%D0%BC)
 */
public class SimpleMerger {

    private int[] unsorted, sorted;

    public SimpleMerger( int[] unsorted ) {
        this.unsorted = unsorted;
    }

    /**
     * Собственно здесь производится разбиение входного массива и запуск рекурсивного алгоритма
     */
    public void sort() {
        int middle;
        int[] left, right;

        if ( unsorted.length <= 1 ) {
            sorted = unsorted;
        } else {
            middle = unsorted.length / 2;

            left = new int[middle];
            right = new int[unsorted.length - middle];

            System.arraycopy( unsorted, 0, left, 0, middle );
            System.arraycopy( unsorted, middle, right, 0, unsorted.length - middle );

            // Внимание! Опа, рекурсия :)
            SimpleMerger leftSort = new SimpleMerger( left );
            SimpleMerger rightSort = new SimpleMerger( right );

            leftSort.sort();
            rightSort.sort();

            sorted = merge( leftSort.getSorted(), rightSort.getSorted() );
        }
    }

    /**
     * Статический метод. Мержит два отсортированных массива
     * Используется и в многопоточной версии сортировки
     */
    public static int[] merge( int[] leftPart, int[] rightPart ) {
        int cursorLeft = 0, cursorRight = 0, counter = 0;
        int[] merged = new int[leftPart.length + rightPart.length];

        while ( cursorLeft < leftPart.length && cursorRight < rightPart.length ) {
            if ( leftPart[cursorLeft] <= rightPart[cursorRight] ) {
                merged[counter] = leftPart[cursorLeft];
                cursorLeft++;
            } else {
                merged[counter] = rightPart[cursorRight];
                cursorRight++;
            }
            counter++;
        }

        if ( cursorLeft < leftPart.length ) {
            System.arraycopy( leftPart, cursorLeft, merged, counter, merged.length - counter );
        }
        if ( cursorRight < rightPart.length ) {
            System.arraycopy( rightPart, cursorRight, merged, counter, merged.length - counter );
        }

        return merged;
    }

    public int[] getSorted() {
        return sorted;
    }
}

TestMultithreadedMergeSort.java

package ua.rumata.sorters;


import java.util.Random;

public class TestMultithreadedMergeSort {

    public static void main( String[] args ) {

        int arrSize = 15_000_000;
        int[] unsorted = new int[arrSize];
        Random randomizer = new Random();

        // Заполняем массив случайными значениями
        for ( int i = 0; i < arrSize; i++ ) {
            unsorted[i] = randomizer.nextInt( 10_000 );
        }

        // Запускаем секундомер
        long startTime = System.nanoTime();

        // Запускаем сортировку в 1 поток
        SimpleMerger sorter = new SimpleMerger( unsorted );
        sorter.sort();

        long endTime = System.nanoTime();

        // Выводим замерянное время в удобочитаемом виде (в секундах), для этого результат в наносекундах делим на
        // единичку с 9 нулями
        StringBuilder logger = new StringBuilder();
        logger.append( "Single Thread Sort: " );
        logger.append( (double)( endTime - startTime ) / 1_000_000_000 );
        logger.append( " seconds" );

        System.out.println( logger.toString() );

        // Выводим несколько элементов из последовательно выбранных отрезков по 1 000 000 элементов,
        // чтобы убедиться, что массив успешно остортировался
        int[] sorted = sorter.getSorted();
        StringBuilder resDumper = new StringBuilder( "Sorted array examples: " );
        for ( int i = 0; i < 15; i++ ) {
            resDumper.append( sorted[i * 1_000_000 + randomizer.nextInt( 50_000 )] );
            resDumper.append( " | " );
        }

        System.out.println( resDumper.toString() );

        // ========== Многопоточный вариант сортировки ============= //

        // Опять засекаем время
        startTime = System.nanoTime();

        // Натравливаем первый поток на несортированный массив (внутри он разделится на еще несколько, пока их
        // общее количество не достигнет указанного в классе MultiMerger значения MAX_THREADS)
        MultiMerger multiMerger = new MultiMerger( unsorted );
        multiMerger.start();
        // Ждем завершения потока
        try {
            multiMerger.join();
        } catch ( Exception e ) {

        }

        // И опять выводим время
        endTime = System.nanoTime();

        StringBuilder logger1 = new StringBuilder( "// +++++++++++++++++++++ //\r\n" );
        logger1.append( "Multi Thread Sort: " );
        logger1.append( (double)( endTime - startTime ) / 1_000_000_000 );
        logger1.append( " seconds" );

        System.out.println( logger1.toString() );

        // а потом опять примеры сортированного массива
        sorted = multiMerger.getSorted();
        StringBuilder resDumper1 = new StringBuilder( "Sorted array examples: " );
        for ( int i = 0; i < 15; i++ ) {
            resDumper1.append( sorted[i * 1_000_000 + randomizer.nextInt( 50_000 )] );
            resDumper1.append( " | " );
        }

        System.out.println( resDumper1.toString() );
    }
}

классные сорты! не могу найти твои контакты. если ты не против, я бы уточнил пару вопросов по коду. добавь меня в скайпе akhambir .