Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Помимо того что это не inplace (который был существенной частью оригинальной статьи), и как отметил Александреску тут совсем другой partition, тут ещё не используется приём дающий гарантию на логарифмичестий размер стека worst case, описанный в той же самой оригинальной статье шестидесятых годов.

Насчет in-place согласен

qsort [] = []
qsort xs = qsort (filter (< pivot) xs) ++ qsort (filter (>= pivot) xs)
  where pivot = xs !! (length xs `div` 2)

Это устраняет проблему выбора первого элемента — как и в оригинале теперь выбирается средний элемент. Сложность алгоритма остается та же O(N*logN)
Правда теряется устойчивость сортировки (хотя это можно исправить)

Здравствуйте, Evgeny.Panasyuk, Вы писали:

EP>Помимо того что это не inplace (который был существенной частью оригинальной статьи), и как отметил Александреску тут совсем другой partition, тут ещё не используется приём дающий гарантию на логарифмичестий размер стека worst case, описанный в той же самой оригинальной статье шестидесятых годов.

qsort [] = []
qsort xs = qsort (filter (< pivot) xs) ++ qsort (filter (>= pivot) xs)
  where pivot = xs !! (length xs `div` 2)

Это устраняет проблему выбора первого элемента — как и в оригинале теперь выбирается средний элемент. Сложность алгоритма остается та же O(N*logN)
Правда теряется устойчивость сортировки (хотя это можно исправить)


P.S. Насчет in-place согласен