Доброго времени суток!

Есть задание: структура данных - дек, отсортировать элементы структуры методом "сравнение и подсчет". Примерное описание метода сортировки:

В методе подсчета сравнений используется вспомогательный массив, который обнуляется. Организуется цикл, в котором происходит подсчет для каждого элемента исходного массива количество элементов, в которые меньше данного и это число записывается в спомогательный массив (если сортировка по возрастанию). Затем берутся элементы из вспомогательного массива, они увеличиваются на 1 (это число k) и уже упорядоченый массив образуется путем постановки на k место упорядоченного массива элементов исходного массива.

Загвоздка в том, что в программе вообще нельзя использовать массив (любые дргие структуры использовать можно). Как избавиться от вспомогательного массива, я еще представляю, а вот как грамотно отсортировать дек...не понимаю. Буду рад предложениям (ссылкам по теме).

Не понял.

 
и при этом 

  

Дело в том, что я нашел описание алгоритма только при использовании массивов. Мне же требуется использовать методы дека и любой другой структуры данных, но только не массивы. 

Можно сделать эмуляцию через файлы.

Используй списки, например.

Да, я хочу их использовать, однако не понятно, как сделать вот эту вещь в списках

Вероятно, для дэка нужно реализовать метод добавления элемента по индексу.