Самый быстрый вид для небольших коллекций

Question

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

• Массивы
• (массив) списки

размером 8-15 элементов следующих типов:

• целое число
• строка из 10-40 символов

Я перечисляю типы элементов, потому что некоторые алгоритмы выполняют больше операций сравнения и меньше операций подкачки.

Я рассматриваю сортировку слиянием, быструю сортировку, сортировку по вставке и сортировку по оболочке (2 ^ k - 1 шаг).

Answer 1

Arrays.sort(..) / Collections.sort(..) примет это решение за вас.

Например, реализация openjdk-7 Arrays.sort(..) имеет INSERTION_SORT_THRESHOLD = 47 - она ​​использует сортировку вставкойдля тех, у кого менее 47 элементов.

Answer 2

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

Но совет @ Божо здоров, как и комментарий @Sean Patrick Floyd.

---

Followup

Если вы считаете, что разница в производительности будет существенной для вашего варианта использования, то вам следует воспользоваться некоторыми реализациями различных алгоритмов и протестировать их, используя фактические данные, с которыми ваше приложение должно иметь дело. (И если у вас еще нет данных, слишком рано начинать настройку приложения, поскольку производительность сортировки будет зависеть от фактических данных.)

Короче говоря, вам нужно самостоятельно провести сравнительный анализ.

Answer 3

Если вы не можете доказать, что это узкое место, то встроенные сортировки в порядке:

Collections.sort(myIntList);

Arrays.sort(myArray);