Обычно очередь сортируется по порядку вставки - элементы сортируются по порядку, в котором они были вставлены в очередь. Похоже, вы хотите нарушить это важное качество очереди.
Я собираюсь покрыть сортировку слиянием этим ответом. Надеемся, что другие расскажут о других алгоритмах, или вы можете получить их самостоятельно.
Один связанный список можно рассматривать как список списков, просто зная, когда один список заканчивается, а другой начинается. Для сортировки слиянием необходимо начинать с отсортированных списков - если каждый список имеет длину 1, он сортируется просто потому, что другой порядок невозможен. Объединить два связанных списка в один легко - вы берете наименьший элемент из каждого из двух списков и связываете его в новый список, пока оба списка не будут исчерпаны. Таким образом, для первого прохода вы разбиваете список на подсписки длины 1 и объединяете их в подсписки длины 2. На втором этапе вы объединяете подсписки длины 2 в подсписки длины 4. Каждый проход удваивает размер отсортированных подсписков , Вы закончили, когда размер отсортированного подсписка больше или равен размеру всего вашего списка.