Block Sort Algorithm

Question

From the Wikipedia page for block sort I figured out that block sort works by dividing the initial array into small subarrays of length 16 for example, sorting all those subarrays in O(n) time, then merging all these blocks in a way I can't understand.

For example, considering an array of length 16, dividing it in 4 block, each of length 4, and sorting those blocks, we get:

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

Can anyone please explain me how does merge step works?

Answer 1

Usually merge sort goes even further and splits the array in blocks of 2. To merge, it creates a pointer to the beginning of both blocks and compares their values. It picks the smaller and increments the corresponding pointer.

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

Pick 1, because its smaller, and update pointer

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

Pick 2

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

Pick 3 and so on....

These values are put on an array which will be compared with another array created with the same technique. And it goes on and on, merging until all the members are sorted. I'm not considering the endless optimizations that you could do in a real merge algorithm.