Number of swaps

[TS60]

Hi, I wanted to ask about the complexity of the number of swaps/moves/assignments that come from the merging algorithm. The table only gives the complexity of the comparisons and extra memory used.

The description about the merging algorithm let it sound similiar to Symmerge and Recmerge:

A rotate merge sort uses rotations to partition two sorted arrays until they're small enough to be merged using auxiliary memory. Blitsort does so by taking the center element of the first array, using a binary search to find all elements smaller than the center element in the second array, and performing an array rotation. It does so recursively until a partition becomes small enough to be merged.

It probably recursively halves the size and rotates. I assume, the number of swaps/moves/assignments is O(m*Log2(m+n)) for two sorted sequences of sizes m and n, where m <= n. This would then result in a total complexity for blitsort of O(N*Log2(N)) comparisons and O(N*Log2(N)*Log2(N)) swaps/moves, if my assumption is correct. This would also be in line with the observation:

Performance on larger arrays degrades steadily

To sum up my question: Has blitsort a total worst-case complexity of O(N*Log2(N)) or O(N*Log2(N)*Log2(N))?

[scandum]

It's technically n log(n)² moves, but the number of moves is reduced by a large constant.. so I've left it kind of vague, as blitsort is still faster than alternative algorithms that are technically n log(n) moves, but introduce a large k.

[TS60]

Thanks for the quick answer!