Алгоритм сортировки блоков

Question

Со страницы Википедии для block sort Я понял, что эта сортировка блоков работает путем деления исходного массива на небольшие подмассивы длиной 16, например, сортировки всех этих подмассивов в O (n) времени, а затем слияния всех этих блоков в способ, который я не могу понять.

Например, рассматривая массив длиной 16, разделив его на 4 блока, каждый длиной 4 и сортировка этих блоков, мы получаем:

10 1 8 3 4 19 20 13 14 17 8 9 12 18 7 20 
10 1 8 3 ----- 4 19 20 13 ----- 14 17 8 9 ----- 12 18 7 20 
1 3 8 10 ----- 4 13 19 20 ----- 8 9 14 17 ----- 7 12 18 20 

Может кто-нибудь, пожалуйста, объясните мне, как это объединить шаг работы ?

Answer 1

Обычно сортировка слияния идет еще дальше и разбивает массив на блоки из 2. Чтобы объединить, он создает указатель на попрошайничество обоих блоков и сравнивает их значения. Он выбирает меньшее и увеличивает соответствующий указатель.

1 4 5 ... 
^ 
2 3 4 ... 
^ 

Pick 1, потому что его меньше, и обновить указатель

1 4 5 ... 
^
2 3 4 ... 
^ 

Pick 2

1 4 5 ... 
^
2 3 4 ... 
^

Pick 3 и так далее ....

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