Bucket sort — это сортировка с линейным временем.
Почему мы используем в нем сортировку вставками? Мы знаем, что сортировка вставками занимает время O(n2). Почему мы не можем использовать линейную сортировку внутри него? Как видим, когда в каждом сегменте мы используем сортировку вставками O(n2). Какова общая сложность сортировки ведра O (n)? Почему мы не используем сортировку O(nlogn), такую как сортировка слиянием или быстрая сортировка?
Сортировка ведрами с сортировкой вставками в ведрах разумна только тогда, когда мы можем ожидать, что в каждом ведре будет только несколько элементов. Когда элементов всего несколько, сортировка вставками подходит.
В реальной жизни такое случается не так уж часто. Обычно это когда мы ожидаем, что данные будут распределены равномерно, потому что мы сортируем по хэш-порядку или что-то в этом роде.
Сортировка сегментов чаще всего используется, когда сортируется целиком, т. е. сегменты вообще не нужно сортировать, и вы можете просто добавить каждый элемент в список сегментов.
Иногда мы выполняем сортировку по основанию сверху вниз, что похоже на сортировку ведра, а затем сортировку ведра для каждого ведра. В сочетании с сохранением битовой маски непустых сегментов это может быть очень быстрый способ сортировки, когда ключи сортировки являются 32-битными целыми числами.
Вы также можете выполнять сортировку по основанию снизу вверх, многократно сортируя ведро по разным диапазонам битов и просто добавляя элементы в каждое ведро. Этот тип сортировки ведра стабилен, поэтому, когда вы сортируете ведро по старшим битам, связи нарушаются предыдущим порядком, который вы получили, сортируя по младшим битам.
сортировка вставками занимает время O(n2).
Это не вся история. Для частично отсортированных массивов хорошо работает сортировка вставками, она имеет линейную временную сложность.
Массив, в котором каждая запись находится недалеко от своей конечной позиции, является типичным примером частично отсортированного массива. Это относится и к сортировке Bucket.
