Предполагая, что вы имеете в виду http://en.wikipedia.org/wiki/American_flag_sort,, тогда, как указано в верхней части статьи, вы можете запустить это на месте (хотя тогда это не стабильная сортировка). Основная идея состоит в том, чтобы иметь указатель на первый не прочитанный элемент, первоначально 0, и временную переменную для хранения одного элемента.
В качестве первого шага вы смотрите на указатель и поднимаете предмет, на который он указывает. Теперь вы можете использовать индексы, чтобы поставить его на место. Если его место не является той позицией, с которой вы изначально читали, вы собираетесь перезаписать другой элемент, поэтому вы меняете элемент, который вы выбрали, на элемент, который вы перезаписали, и теперь вы держите другой временный элемент - и посмотрите вверх, чтобы увидеть куда он должен идти и продолжать.
В конце концов вы поместили что-то в место, из которого вы читаете, так что вы можете увеличивать указатель чтения, пропуская области, где вы уже написали отсортированные элементы, поднимать другой элемент и продолжать, пока все не будет отсортировано.