Быстрая сортировка — нестабильная сортировка.

В определении быстрой сортировки само по себе нет ничего, что делало бы ее стабильной или нестабильной. Это может быть и то, и другое.

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

Хотя этот метод разбиения, безусловно, распространен, не требуется, чтобы алгоритм был быстрой сортировкой. Это просто метод, который является простым и распространенным при применении быстрой сортировки к массиву.

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

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

node *list1 = dummy_node1;
node *add1 = list1;
node *list2 = dummy_node2;
node *add2 = list2;

T pivot = input->data; // easiest pivot value to choose

for (node *current = input; current != nullptr; current = current->next)
    if (current->data < pivot) {
        add1->next = current;
        add1 = add1 -> next;
    }
    else {
        add2->next = current;
        add2 = add2->next;
    }
add1->next = nullptr;
add2->next = nullptr;