рекурсивная сортировка разделением

[blackbanny]

ниже привел код рекурсивной сортировки разделением, но она сортирует нормально, если в массиве представлены только уникальные элементы, а если появляются одинаковые, то зацикливается...
не могу понять в чем дело...
вызов в main Qsort(0, a.size-1); где a - объект класса vector

template <class T> void vector<T>::Qsort(int l, int r)
{
   if(l < r)
   {
           int k = Partition(l, r);
           Qsort(l, k);
           Qsort(k+1, r);
   }
}
 
template <class T> int vector<T>::Partition(int l, int r)
{
        T x = array[(l+r)/2];  
        int i = l;
        int j = r;
        while(1)
        {
           while(array[j] > x)
           {
                   j--;
           }
           while(array[i] < x)
           {
                   i++;
           }
           if(i < j)
           {
                   T t = array[i];
                         array[i] = array[j];
                         array[j] = t;
           } else return j;
        }
}

[MBo]

сравни с циклом do-while здесь:
http://algolist.ru/sort/quick_sort.php

[blackbanny]

нашел ошибку...
нужно здесь:

if(i < j)
           {
                   T t = array[i];
                         array[i] = array[j];
                         array[j] = t;
           }

добавить i++; j--; вот так:

if(i < j)
           {
                   T t = array[i];
                         array[i] = array[j];
                         array[j] = t;
                         i++;
                         j--;
           }