Javascript + Quicksort: как эта реализация википедии работает?

Question

Я пытаюсь подстроить свою javascript + алгоритм игры. Я смотрю на эту реализацию быстрой сортировки на википедии: http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting/Quicksort#JavaScript

function qsort(a) { 
    if (a.length == 0) return []; 

    var left = [], right = [], pivot = a[0]; 

    for (var i = 1; i < a.length; i++) { 
    a[i] < pivot ? left.push(a[i]) : right.push(a[i]); 
    } 

    return qsort(left).concat(pivot, qsort(right)); 
} 

Я понимаю концепцию. Он рекурсивно разбивает исходный массив на более мелкие части и сортирует меньшие массивы. Однако я не вижу, как работает эта функция qsort, когда она никогда не возвращает массивы влево/вправо (что-то вроде return leftArrayResult;). Разве это не означает, что qsort всегда возвращает null или пустой массив? Итак, qsort(left).concat(pivot, qsort(right) всегда будет null.concat(pivot, null) и поэтому никогда не работает?

Answer 1

Если мы имеем несортированную [6,10,4,1],

Первая фаза:

qsort[6,10,4,1];

pivot = 6;

В течение цикла с каждым проходом цикла пронумерованным:

1. 10 > 6, добавляется в правой массив
2. 4 < 6, добавлен налево массив
3. 1 < 6, добавлен налево массив

left = [4,1]; right = [10]; pivot = 6;

QSort Затем вызывается рекурсивно на левом массива, который снова [4,1].

Вторая фаза:

pivot = 4

В течение цикла с каждым проходом цикла пронумерована:

1. 1 < 4, добавлен в левый массив

left = [1]; right = []; pivot = 4;

qsort затем вызывается рекурсивно, а в левом массиве - [1].

Третий этап:

pivot = 1

для цикла не выполняется.

left = []; right = []; pivot = 1;

QSort вызывается левой массивом.

Четвертая фаза:

На этот раз QSort возвращает пустой массив.

Выполнение теперь переходит к concat-вызову в третьем стеке, беря пустой массив и объединяет его в 1 и результат qsort(right), который также возвращает пустой массив. Таким образом, возвращаемое значение теперь равно [1].

Выполнение теперь возвращается к второму этапу, где [1] объединяется с осью 4 и результатом qsort([]), поэтому теперь мы имеем возвращаемое значение [1,4].

Выполнение теперь возвращается к первой фазе, поэтому мы объединяем результат [1,4] с осью 6 и результатом qsort([10]), чтобы получить наш результат от [1,4,6,10].

Надеюсь, этого достаточно просто понять!