This claims to be a stable in-place sort and doesn’t seem outrageously complicated. I haven’t verified that it is stable, in-place, or in fact a sort at all.
It’s O(n log^2 n) because it merges subarrays using something like STL’s inplace_merge which is O(n log n). Devising an O(n) in-place merge, and thus an O(n log n) merge sort, is much harder. GrailSort and WikiSort have working implementations, both are over 500 lines.
This claims to be a stable in-place sort and doesn’t seem outrageously complicated. I haven’t verified that it is stable, in-place, or in fact a sort at all.
It’s O(n log^2 n) because it merges subarrays using something like STL’s inplace_merge which is O(n log n). Devising an O(n) in-place merge, and thus an O(n log n) merge sort, is much harder. GrailSort and WikiSort have working implementations, both are over 500 lines.
Ah, good catch.