Looking through your code and the paper you linked, it looks like what you're doing is more or less what they describe in the introduction-- element by element merge that will require O(N) moves and O(m log (n/m)) comparisons for two lists, with appropriate multipliers as in my other post for performance on multiple lists.
The next fancier way to do it (section 2.2) is that rather than swapping one element at a time, keep going up the subset until you get to an element that you can't swap in (because it's bigger than the next number in the sequence you're going into) and then do a block move of everything up to that point, swapping into the buffer as needed. This idea of moving a group at a time is where the faster algorithms come in. Section 2.3 is the same thing, but blockwise-- break each list into blocks (say of sqrt(Gsize)) and compare the starts and ends of those, and move whole blocks when possible, partial blocks when necessary, and storing in the buffer. The buffer is apparently where stability gets lost, if its ordering gets munged too badly. But this block swapping (is this whole block able to fit before that one?) is the basis for the faster algorithm.
The stuff between 2.3 until 4.0 looks like mostly history and distraction from the algorithm in 4.0-4.3, where block exchange looks like my triple reverse from last week:). In the worst case (sublists like [1,4,7,...][2,5,8,...][3,6,9,...]) it should end up performing like the one element at a time algorithm, but in cases where there are runs that fit inside each other, you'll approach the limiting performance.
Edit about an hour later...:Here's what I hope is an almost self explanatory example using only Block_Exchange (if I did it right). You start with the two leftmost groups, figure out where you need to put the left, right, and center of a block_exchange, then you do it, adjust your three pointers, then repeat. When you get to the next presorted group you start over again. For small samples it doesn't look like much, but if you have big sparse lists it's probably somewhat better than bubbling individual elements into place
]= rightmost point of a sorted subgroup [= leftmost point of a sorted subgroup | indicate the ends of the block_exchange points ^ indicates the center about which the exchange is made [ 1 7 15 32] [3 17 54 63][27 35 59 60][11 23 24 29] [ 1 |7 15 32]^[3 17| 54 63][27 35 59 60][11 23 24 29] [ 1 |7 15 32]^[3 |17 54 63][27 35 59 60][11 23 24 29] [ 1 3 ][7 15| 32]^[17 |54 63][27 35 59 60][11 23 24 29] [ 1 3 7 15 17| 32 54 63]^[27| 35 59 60][11 23 24 29] [ 1 3 7 15 17 27 32 |54 63]^[35| 59 60][11 23 24 29] [ 1 3 7 15 17 27 32 35 54 |63]^[59 60]|[11 23 24 29] [ 1 3 7 |15 17 27 32 35 54 59 60 63]^[11| 23 24 29] [ 1 3 7 11 15 17 |27 32 35 54 59 60 63]^[23 24| 29] [ 1 3 7 11 15 17 23 24 27| 32 35 54 59 60 63]^[29]| [ 1 3 7 11 15 17 23 24 27 29 32 35 54 59 60 63]
In reply to Re: Can you improve upon my algorithm.
by bitingduck
in thread Can you improve upon my algorithm.
by BrowserUk
| For: | Use: | ||
| & | & | ||
| < | < | ||
| > | > | ||
| [ | [ | ||
| ] | ] |