Можно ли оптимизировать сортировку?

Question

[rsatarov]

Нашел специфический алгоритм, называется "Circle Sort". Он сравнивает крайние элементы массива, постепенно доходя до середины, а потом рекурсивно сортирует свои меньшие части. Правда, за раз он не всегда все делает, поэтому нужно пройтись несколько раз. Согласно рекомендации, его можно оптимизировать, если после 0,5 log(n) кругов все добить сортировкой вставками. Скорость, конечно, так себе, но выглядит интересно. Но можно ли из него выжать еще больше, допустим, избавившись от рекурсии? (И сильно ли рекурсия влияет на скорость?)

public void sort(int[] array) {
    int numOfSwaps = 0;

    for (int i = (int) (0.5 * Math.log(array.length)); i >= 0; i--) {
        numOfSwaps = circleSort(array, 0, array.length - 1, 0);
    }

    if (numOfSwaps != 0) {
        for (int i = 1; i < array.length; i++) {
            int temp = array[i];
            int j = i;

            while (j > 0 && array[j - 1] > temp) {
                array[j] = array[j - 1];
                j = j - 1;
            }
            array[j] = temp;
        }
    }
}

private int circleSort(int[] array, int lowerBound, int higherBound, int numOfSwaps) {
    if (lowerBound == higherBound) return numOfSwaps;

    int low = lowerBound;
    int high = higherBound;
    int middle = (higherBound - lowerBound) / 2;

    while (lowerBound < higherBound) {
        if (array[lowerBound] > array[higherBound]) {
            int temp = array[lowerBound];
            array[lowerBound] = array[higherBound];
            array[higherBound] = temp;
            numOfSwaps++;
        }
        lowerBound++;
        higherBound--;
    }

    if (lowerBound == higherBound && array[lowerBound] > array[higherBound + 1]) {
        int temp = array[lowerBound];
        array[lowerBound] = array[higherBound + 1];
        array[higherBound + 1] = temp;
        numOfSwaps++;
    }

    numOfSwaps = circleSort(array, low, low + middle, numOfSwaps);
    numOfSwaps = circleSort(array, low + middle + 1, high, numOfSwaps);

    return numOfSwaps;
}

Comments

[Евгений Шатунов]

В код я не смотрел, поэтому на ответ, а коммент. Однако, по описанию это никакой не circle sort, это quick sort с кривоватой и слабо понятной реализацией. Его можно и переписать более компактно, и эффективность повысить. В коде написаны, прям говоря, страсти...
algolist.manual.ru/sort/quick_sort.php

[Артур Нуруллин]

Вместо рекурсии лучше stack.