Что не так с этой реализацией QuickSort?

Question

У меня есть следующее:

function quickSort(array, low, high) {
    var len = array.length,
        l = low || 0,
        r = high || len - 1,
        m = Math.round((l + r) / 2),
        t;

    do {
        while (array[l] < array[m]) {
            l += 1;
        }
        while (array[r] > array[m]) {
            r -= 1;
        }

        if (l <= r) {
            if (l < r) {
                t = array[r];
                array[r] = array[l];
                array[l] = t;

                console.log('Swapped ' + array[r] + ' with ' +
                                         array[l] + '. ' +
                                         array);
            }

            l += 1;
            r -= 1;
        }
    } while (l <= r);

    if (r > 0) quickSort(array, 0, r);  
    if (l < len - 1) quickSort(array, l, len - 1);
}

Используя его следующим образом:

var initial = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10], // Duplicate, just to compare
    sorted  = [1, 8, 9, 0, 2, 5, 6, 7, 3, 4, 10];

quickSort(sorted);

console.log('Initial: ' + initial + '\nSorted:  ' + sorted);

Удивительно, но после сортировки массива код выдает stack_overflow.Наверное, мне не хватает условия выхода из рекурсии, но я не знаю где.

Answer 1

Редактировать (заменяя предыдущий ответ) : Я считаю, что проблема заключается в том, как вы устанавливаете переменную len. Для сортировки на месте len должна быть только длиной части сортируемого массива, а не всего массива, иначе ваши сравнения в конце никогда не оценятся как ложные. Так что вместо:

var len = array.length,
    l = low || 0,
    r = high || len - 1;

Вам необходимо установить len на основе l и r:

var l = low || 0,
    r = high || array.length - 1,
    len = r-l;

Вы можете увидеть работающий jsFiddle здесь: http://jsfiddle.net/nrabinowitz/PPeh9/6/ - я заменил ваши тестовые данные случайным массивом для тестирования.