Сортировка последовательности относительно середины

[RAFA91]

Нашел в литературе алгоритм сортировки относительно середины массива.

Но он работает не для всех последовательностей. К примеру если применить этот алгоритм к

int a[]={5,10,7,6,3,9,4,8,12};

средний элемент тут имеет значение 3

то после применения алгоритма получим 3 10 7 6 5 9 4 8 12 число 10 явно не в той части .

#include <iostream>
using namespace std;
 
void qsort (int a[], int lef, int rit);
 
int main() 
{
    int a[]={5,10,7,6,3,9,4,8,12};
    for (int i=0;i<9;i++) cout<< a[i]<<" "; cout<< endl;
    qsort (a, 0, 8);
    for (int i=0;i<9;i++) cout<< a[i]<<" "; cout<< endl;
    return 0;
}
 
void qsort (int a[], int lef, int rit)
{
int ir, rm, buf; // ir – для индекса среднего элемента
// текущей части массива.
// rm – для значения среднего
// элемента текущего массива.
// buf – для промежуточных значений
// обрабатываемой информации.
int l1, r1; // l1 – для индекса элемента, который
// расположен левее и
// больше среднего.
// r1 – для индекса элемента, который
// расположен правее и
// меньше среднего.
int i; // i – для управляющего параметра цикла.
l1 = lef; // Определяем начальный индекс текущей
// части массива.
r1 = rit; // Определяем конечный индекс текущего
// массива.
ir = (l1+r1)/2; // Определяем индекс среднего элемента
// текущей части массива.
rm = a[ir]; // В rm пересылаем значение среднего
// элемента текущего массива.
do // Цикл для перебора элементов, которые
// находятся левее и правее среднего
// элемента текущей части массива.
{
while ( a[l1] < rm ) l1++; // Находим 1-й элемент, который лежит
// слева и больше среднего элемента.
// Индекс этого элемента фиксируется
// в переменной l1.
while ( a[r1] > rm ) r1--; // Находим 1-й элемент, который лежит
// справа и больше среднего элемента.
// Индекс этого элемента фиксируется
// в переменной r1.
if ( l1 <= r1 ) // Начало перестановки элементов
// массива. Меньший относительно
// среднего переставляем в позицию l1,
// а больший относительно среднего
// переставляем в позицию r1 и директивами
// l1++; и r1++; переходим к рассмотрению
// следующих элементов, расположенных
// соответственно левее и правее среднего элемента.
{
// Переставляем элементы массива.
buf = a[l1];
a[l1] = a[r1];
a[r1] = buf;
l1++;
r1--;
} // Конец перестановки элементов массива.
}
while ( r1 > l1 );
}

http://ideone.com/BuhKKh