Quicksort provoque un débordement de pile

Question

J'ai le code suivant, (pris ici), mais il provoque une exception stackoverflow quand il y a deux valeurs identiques dans la liste à trier.

Quelqu'un peut-il m'aider à trouver la cause de ce problème ?

 public static IEnumerable<int> QSLinq(IEnumerable<int> _items)
{
    if (_items.Count() <= 1)
        return _items;

    var _pivot = _items.First();

    var _less = from _item in _items where _item < _pivot select _item;
    var _same = from _item in _items where _item == _pivot select _item;
    var _greater = from _item in _items where _item > _pivot select _item;

    return QSLinq(_less).Concat(QSLinq(_same)).Concat(QSLinq(_greater));
}

Answer 1

Vous ne devriez pas faire un appel récursif à trier _same - vous savez qu'il est trié, puisque toutes les valeurs sont les mêmes !

Answer 2

Mais ce n'est pas tout : le fait de choisir le premier élément comme pivot et de ne pas trier d'abord le plus petit sous-réseau fera également déborder votre pile.