=algorithm
Recently, I've been forced to think about sorting algorithms (if you know what I mean) and I thought I'd at least try to do something productive.
In many software libraries,
quicksort is the
default sorting algorithm, and
merge sort is the
default stable sort algorithm.
Merge sort has better data locality
than quicksort, which makes it faster when using hard drives or highly
pipelined architectures. The advantage of quicksort over merge sort is that
it's in-place. Not needing large memory allocations is also why quicksort is
sometimes faster than merge sort.
Is it possible to do a merge sort
in-place efficiently?
Obviously, if an algorithm is in-place, then data must be
placed where there is space for it. My proposal for doing that with
merge sort is as follows:
1) divide
data into blocks
2) put blocks of data where there's space, and track
where blocks are placed
3) take blocks of data from where they are
4)
repeat steps (2) and (3)
5) sort the blocks
Block size and memory
requirements should be approximately sqrt(n).
I didn't find any
papers on this approach, but it's such a simple idea that I assume it's been
done before.
Suppose we denote blocks of data as:
{a, b, c, d}
when there are 4 runs
{A, B} when there are 2 runs
{S} when there is
one run (sorted)
Here is an example of sorting an array:
aaaabbbbccccdddd
aaaa__bb ccccdddd
Merging of {a, b} into {A} and {c, d} into {B} starts. The blocks of {a, b} are read into a buffer, starting with the first ones. When blocks are used completely, they're cleared in the main array. Here, {b} is first in the sort, so blocks of {b} are cleared first.
aaaaAAbb
ccccdddd
45______ ________
The merged run data {A} is written into the space left by cleared {b} blocks. The locations are stored in a locations array. Here, locations[i] is the index where the ith output data block can be found.
AAAAAAAA
BBBBBBBB
45670123 45670123
Here, {a, b, c, d} are fully merged into {A, B} and the locations are stored.
AAAA__AABBBBBBBB
{A, B} merging starts. Here, the first blocks of {A} (which are in the middle of the array) are cleared first.
AAAASSAABBBBBBBB
____01__________
For the final round, locations[i] is the location where the ith data block should go. Once all runs are merged, the blocks are sorted.
update: here's an implementation of this concept