void quickSort (int a[], int l, int r)
{
        // Вопрос: мы работаем с полуоткрытым интервалом или с закрытым? [l..r) или [l..r] ?
        // Ладно, обозначим правую границу загадочным }
        
    int i = l;
    int j = r;
    int x = a[(l + r) / 2];
    // почему в роли медианы взяли значение из середины массива?
    // при каких условиях здесь произойдёт вылет за границы?
    
    // инвариант цикла: a[l..i} < x < [j..r}
    // на каждой итерации диапазон [i..j} сужается
    // постусловие - a[i..j} == x (причём очевидно, что этот интервал не пуст, ведь ему принадлежит медиана)
    do
    {
        while (a[i] < x) i++; // кажется, всё-таки работаем с закрытыми интервалами
        while (x < a[j]) j--;
        
        // замечательный сплав swap() и автоинкрементов, очень "интуитивно"
        if (i <= j)
        {
            int temp = a[i];
            a[i++] = a[j];
            a[j--] = temp;
        }
    }
    while (i <= j); // Зачем проверку диапазона делаем только после первой итерации? Она что, раньше нам не нужна?
    
    if (l < j) quickSort (a, l, j);
    if (i < r) quickSort (a, i, r);
}

M>void quickSort (int a[], int l, int r)
M>{
M>    int i = l;
M>    int j = r;
M>    int x = a[(l + r) / 2];
M>    do
M>    {
M>        while (a[i] < x) i++;
M>        while (x < a[j]) j--;
M>        if (i <= j)
M>        {
M>            int temp = a[i];
M>            a[i++] = a[j];
M>            a[j--] = temp;
M>        }
M>    }
M>    while (i <= j);
M>    if (l < j) quickSort (a, l, j);
M>    if (i < r) quickSort (a, i, r);
M>}
M>

//от работы с элементами списка перешли к работе 
// с индексами (хотя в описании алгоритма про индексы ни слова)
int i = l; int j = r; 

// да это же обмен значениями! ну и конечно очевидно, 
// что вместе с обменом значениями передвигаются и указатели 
int temp = a[i]; a[i++] = a[j]; a[j--] = temp; на элементы (индексы)

// легко! поиск элемента (<x)
while (a[i] < x) i++;

// легко! поиск элемента (>x) 
while (x < a[j]) j--;

// а точно! мы же просматриваем массив сразу с двух сторон, 
// а это условие завершения
do ... while (i <= j);

M>quickSort [] = []
M>quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]
M>

quickSort (x:xs) = quickSort [y | y <- xs, y < x] ++ [x] ++ quickSort [y | y <- xs, y >= x]

foreach(элем1:список1)
  foreach(элем2:список2)
    ..
    if (условие1 и условие2 и ...)
      посчитать что_хотим_получить и включить это значение в результат
    end
  end
end

qsort (x:xs) = qsort lesser ++ [x] ++ qsort greater
  where lesser  = filter (<x) xs
        greater = filter (>=x) xs

-- Вариант 0 (quick sort "в лоб")
qsort0 [] = []
qsort0 (x:xs) = qsort0 (filter (<x) xs) ++ [x] ++ qsort0 (filter (>=x) xs)

-- Вариант 1 (мой вариант) - один проход по списку
-- сортировка относительно середины списка
qsort2 [] = []
qsort2 xs = qsort2 lesser ++ equals ++ qsort2 greater
  where (lesser,equals,greater) = split mean xs
        mean = xs !! (length xs `div` 2)

split mean xs = split' [] [] [] xs
  where split' ls es gs [] = (ls,es,gs)
        split' ls es gs (p:ps) | p < mean  = split' (p:ls) es     gs     ps
                               | p == mean = split' ls     (p:es) gs     ps
                               | p > mean  = split' ls     es     (p:gs) ps

-- Вариант 1 (dmz / z00n)
qsort3 x = qsort3' x []

qsort3' [] y = y
qsort3' [x] y = x:y
qsort3' (x:xs) y = part xs [] [x] []  
    where
        part [] l e g = qsort3' l (e ++ (qsort3' g y))
        part (z:zs) l e g 
            | z > x     = part zs l e (z:g) 
            | z < x     = part zs (z:l) e g 
            | otherwise = part zs l (z:e) g

Сортируемый список --> Алгоритм сортировки	Случайные значения	Отсортированные значения	В обратном порядке
Вариант 0 ("простая программа" на Haskell)	1.06 sec / 10 Mb 103.77 sec / 92 Mb	480.72 sec / 7 Mb * Более 600 sec *	* out of memory * * out of memory *
Вариант 1 (мой)	0.17 sec / 12 Mb 1.86 sec / 122 Mb	0.17 sec / 6 Mb 2.08 sec / 56 Mb	0.16 sec / 6 Mb 2.03 sec / 56 Mb
Вариант 2 (dmz / z00n)	0.08 sec / 6 Mb 1.08 sec / 57 Mb	258.28 sec / 7 Mb * Более 600 sec *	259.47 sec / 7 Mb * Более 600 sec *
Sort из стандартной библиотеки (merge sort)	0.34 sec / 17 Mb 5.67 sec / 150 Mb	0.13 sec / 9 Mb 1.64 sec / 75 Mb	0.16 sec / 12 Mb 1.83 sec / 121 Mb

rnds seed = randomRs (1,1000000) (mkStdGen seed) :: [Int]
list = take n $ rnds seed

qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []

qsort3' [] y     = y   -- +++
qsort3' [x] y    = x:y -- +++
qsort3' (x:xs) y = part xs [] [x] []  
    where
        part [] l e g = qsort3' l (e ++ (qsort3' g y))
        part (z:zs) l e g 
            | z > x     = part zs l e (z:g) 
            | z < x     = part zs (z:l) e g 
            | otherwise = part zs l (z:e) g

Пример 1. Быстрая сортировка Хоара на C.

void quickSort (int a[], int l, int r)
{
    int i = l;
    int j = r;
    int x = a[(l + r) / 2];
    do
    {
        while (a[i] < x) i++;
        while (x < a[j]) j--;
        if (i <= j)
        {
            int temp = a[i];
            a[i++] = a[j];
            a[j--] = temp;
        }
    }
    while (i <= j);
    if (l < j) quickSort (a, l, j);
    if (i < r) quickSort (a, i, r);
}

Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке.

quickSort ([]) = []
quickSort ([h : t]) = quickSort (n | n ∈ t, n <= h) + [h] + quickSort (n | n ∈ t, n > h)

Пример 2 следует читать так:
1. Если список пуст, то результатом также будет пустой список.

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

Пример 3. Быстрая сортировка Хоара на языке Haskell.

quickSort [] = []
quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]

Как видно, даже на таком простом примере функциональный стиль программирования выигрывает и по количеству написанного кода и по его элегантности.

Prelude> let appendEmpty xs = xs ++ []
Prelude> :s +s
Prelude> last $ [1 .. 10000000]
10000000
(0.45 secs, 402126788 bytes)
Prelude> last $ appendEmpty $ [1 .. 10000000]
10000000
(0.55 secs, 683657904 bytes)
Prelude> last $ appendEmpty $ appendEmpty $ [1 .. 10000000]
10000000
(0.72 secs, 964689248 bytes)
Prelude> last $ appendEmpty $ appendEmpty $ appendEmpty [1 .. 10000000]
10000000
(0.87 secs, 1242563408 bytes)
Prelude> last $ appendEmpty $ appendEmpty $ appendEmpty $ appendEmpty [1 .. 10000000]
10000000
(1.08 secs, 1527196932 bytes)

[cut]
PM>Prelude> last $ appendEmpty $ appendEmpty $ appendEmpty $ appendEmpty [1 .. 10000000]
PM>10000000
PM>(1.08 secs, 1527196932 bytes)
PM>

Возьмем такой вариант использования. У тебя массив из миллиона чисел. Тебе надо его отсортировать, и взять первые два десятка элементов. На данном примере с таким кодом на С ты будешь очень долго догонять по скорости Хаскельный вариант.

Prelude> let appendEmpty xs = xs ++ []                                           
Prelude> let xs = [1 .. 10000000]                                               
Prelude> :s +s
Prelude> last xs
10000000
(1.95 secs, 402124972 bytes) -- вот здесь мы исключили влияние времени генерации
Prelude> last xs -- повторный замер показывает, что список уже сгенерирован
10000000
(0.08 secs, 0 bytes)
Prelude> last $ appendEmpty xs                                                   
10000000
(0.18 secs, 281025096 bytes)
Prelude> last $ appendEmpty $ appendEmpty xs                                     
10000000
(0.32 secs, 561513668 bytes)
Prelude>  last $ appendEmpty $ appendEmpty $ appendEmpty xs 
10000000
(0.45 secs, 842527844 bytes)
Prelude>  last $ appendEmpty $ appendEmpty $ appendEmpty $ appendEmpty xs
10000000
(0.60 secs, 1122493452 bytes)
Prelude>

PM>Я думаю, что получается. Это довольно просто проверить, надо всего-то поэкспериментировать с различными длинами списков и построить график, но мне лень .

%% Вот это - достаточно понятно.
concat( [], X ) -> X;

%% Как, собственно, и вот это
concat( [ H | T ], X ) ->
   [ H | concat( T, X ) ].

RD>Мне достаточно наслаждаться жизнью. Доказывать кому-то что-то нужно Вам. А мне и так хорошо.

qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []

qsort3' (x:xs) y = part xs [] [x] []  
    where
        part [] l e g = qsort3' l (e ++ (qsort3' g y))
        part (z:zs) l e g 
            | z > x     = part zs l e (z:g) 
            | z < x     = part zs (z:l) e g 
            | otherwise = part zs l (z:e) g

concat( A, B ) -> reverse_concat( reverse_concat( A, [] ), B ).

reverse_concat( [], B ) -> B;
reverse_concat( [ H | T ], B ) -> reverse_concat( T, [ H | B ] ).

qsort [] = []
qsort xs = qsort lesser ++ equals ++ qsort greater
  where (lesser,equals,greater) = split mean xs
        mean = xs !! (length xs `div` 2)

-- делит список xs на три части, возвращает тупл (элементы меньшие mean, равные mean, большие mean)
split mean xs = split' [] [] [] xs
  where split' ls es gs [] = (ls,es,gs)
        split' ls es gs (p:ps) | p < mean  = split' (p:ls) es     gs     ps
                               | p == mean = split' ls     (p:es) gs     ps
                               | p > mean  = split' ls     es     (p:gs) ps