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?

Sell

The wiki article for block sort has been updated. To keep the sort stable, two groups of unique elements are used for working space, being swapped with elements being merged so the sort is in place. Since the groups contain unique elements, stability will be maintained regardless of where the unique values are swapped to during the merge steps. An improved version of this can be found on github block sort , – Tarragona

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.

Antilogy

Answer 2

The first thing of block sort merging is to extract buffers. That is the only thing I know a lot about, and it starts like this. Find the square root of the array's length, and find that many unique values in the beginning and end. Using either rotations or reversals, you can put them all in the beginning and end. Then, I don't know how to merge the other stuff.

Truss