Данный метод сортировки является улучшением алгоритма сортировки пузырьком. Получен алгоритм Шейкерной сортировки из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.
Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов.
template<class T>
void shakerSort(T a[], long size) {
  long j, k = size-1;
  long lb=1, ub = size-1; // границы неотсортированной части массива
  T x;
  do {
// проход снизу вверх 
    for( j=ub; j>0; j-- ) {
      if ( a[j-1] > a[j] ) {
        x=a[j-1]; a[j-1]=a[j]; a[j]=x;
        k=j;
      }
    }
    lb = k+1;
    // проход сверху вниз 
    for (j=1; j<=ub; j++) {
      if ( a[j-1] > a[j] ) {
        x=a[j-1]; a[j-1]=a[j]; a[j]=x;
        k=j;
      }
    }
    ub = k-1;
  } while ( lb < ub );
}

Среднее количество сравнений, хоть и уменьшилось, но остается O(n2), в то время как число обменов не поменялось вообще никак. Среднее(оно же худшее) количество операций остается квадратичным.
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.