Сортировка слиянием для простого числа элементов?

Question

Насколько я знаю, в сортировке слиянием мы должны разделить элементы на несколько групп. Но если число - простые числа, то как возможно деление? Делим ли мы их на неравные группы? Если вы собираетесь представить реализацию, пожалуйста, сделайте это на C или Python.

Answer 1

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

Вы обычно хотите, чтобы они были близки к одному и тому же размеру (чтобы разделить усилия равномерно, уменьшая сложность сортировки), но даже это не является строго необходимым. Основной алгоритм сортировки слиянием будет работать, даже если вы разделите последовательность длины N на подпоследовательности длины 1 и длины (N-1) (хотя производительность будет паршивой).

Answer 2

Скажем, есть 2k + 1, он будет разделен на две части, k и k + 1

Answer 3

Элементы не обязательно разделяются равномерно, но если у каждой группы будет как можно меньше элементов, это приведет к наименьшей общей сложности.

Это общий принцип для m-way сортировки слиянием, где m обозначает количество групп, которые вы собираетесь иметь.