Рекурсивная сортировка только с массивом в качестве входных данных

Question

Я написал несколько коротких рекурсивных программ и сейчас делаю рекурсивную сортировку. До сих пор я использовал 2 входа, массив и индекс. Существует ли рекурсивный метод сортировки, для которого нужен только массив в качестве входных данных? Я думал, что Bubble Sort подойдет для этого, но он также использует индекс для отслеживания позиции.

И в случае, если кто-то захочет узнать, у меня было HW для создания рекурсивной сортировки (что я уже сделал, используя массив и индекс), это просто для того, чтобы посмотреть, возможно ли это сделать без индекса.

Answer 1

Я считаю, что рекурсивная сортировка слиянием может быть выполнена только с массивом в качестве параметра: http://en.wikipedia.org/wiki/Merge_sort

Редактировать: Я думаю, вы могли бы пропустить индекс следующим образом:

function bubble_sort(arr)
{
    for (i=0 to arr.length-1)
    {
        if(arr[i] > arr[i+1])
        {
            swap(arr, i);
            return bubble_sort(arr);
        }
    }
    return arr;
}

Это не идеальная сортировка пузырьков, поскольку начальный индекс всегда равен нулю.Сложность все еще O (n ^ 2).Если вы готовы клонировать массив (и потратить впустую много памяти), тогда вы можете заменить

return bubble_sort(arr);

на:

return combineArrays(arr.subArray(0, i), bubble_sort(arr.subArray(i, n)));

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