Block sorting algorithm
From the Wikipedia page, block sorting I figured out that block sort works by dividing the original array into small subarrays of 16 length, for example, sorting all of those subarrays in O (n) time, and then concatenating all those blocks in a way that I can't figure out.
For example, given an array of length 16, dividing it into 4 blocks, each of length 4, and sorting these 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 someone explain to me how the merge works?
source to share
Usually, the merge sort goes even further and splits the array into blocks of 2. To merge, it creates a begging pointer for both blocks and compares their values. It chooses the smaller one and increments the corresponding pointer.
1 4 5 ...
^
2 3 4 ...
^
Choose 1 because its smaller and update pointer
1 4 5 ...
^
2 3 4 ...
^
Choice 2
1 4 5 ...
^
2 3 4 ...
^
Choose 3, etc.
These values are placed into an array that can be compared to another array created using the same technique. And it continues and changes until all participants are sorted. I am not covering a lot of optimizations you could make in a real merge algorithm.
source to share