Сортировка подсчетом (counting sort) 

+Адлена Лавлейс благодарю!)

Благодарю🙂

2n или 3n - в итоге берём за n

@@danylosmahliuk8591 почему n + n + k = n + k? Разве не должно быть 2n + k ? Или это как-то по другому работает? И ещё смущает, что в итоге мы получаем не сам упорядоченный массив, а запись из которой его можно разложить. На это же то же потребуются операции?

@@user-ib1kw2ip7c он про то что O(An+B) приблеженно равно O(n)

@@user-ib1kw2ip7c Вместо вывода каждого значения можно помещать его в новый массив, который и получится отсортированным. Или даже перезаписывать старый массив, если он не нужен.

Вы не описали критерий, по которому хотите сортировать, если он определяется уникальным числовым ключом то трогать сами структуры скорее всего нет смысла.

Можно пойти в лоб и создать массив размера n. Если соответствующих значений в исходном массиве нет, то после подсчёта всех чисел соответствующие ячейки будут пустыми. Например, массив {2 9 7 9}, создадим массив для подсчёта из 9 ячеек, после подсчёта получим {0 1 0 0 0 0 1 0 2}. Выводим отсортированный массив: не выводим ни одной единицы, выводим одну двойку, и т.д. Но для такого варианта желательны дополнительные танцы с бубном, если минимальное и/или максимальное значение большое, и необходимы танцы, если есть отрицательные значения...

@@nikelsad та хоть как хотите сортируйте, эта операция не учтена в сложности алгоритма...

Да ничто не мешает отрицательные числа в массив поместить

Не все, а конкретно эта, работает именно с числами, применять целесообразно когда диапазон чисел много меньше сортируемого массива, к примеру массив из миллиона чисел, каждое из которых от 0 до 1000

@@EvgeniyMalov А с чем по-вашему работают остальные сортировки ?

Я имею виду, что сортировать можно не только числа

Вы наверное имеете ввиду, что всегда можно пронумеровать множество и имея порядок и свести к сравнению чисел любую сортировку?

Есть так называемый класс comparsion sort сортировок, они работают на любом множестве элементов с заданным порядком, порядок задаётся предикатом обладающим строго определёнными свойствами, элементы множества не обязательно числа.