我一直在思考函数的基本大O性能， 单独或相互协作。
所以 IPM(S) 是一个对 S 进行就地合并的函数， IPMS(S) 是一个进行就地合并排序的函数。
所以 IPM( [1, 3, 5, 7, 2, 4, 6, 8 ] ) = [ 1, 2, 3, 4, 5, 6, 7, 8 ] , 和 IPMS( [ 7, 5, 3, 1, 8, 6, 4, 2 ] ) = [ 1, 2, 3, 4, 5, 6, 7, 8 ] .
我的问题是：
当前“最先进的”是什么是最好的实现 （n 个大 O 项）用于 IPM 和 IPMS
IPMS 的最佳实施使用最佳实施 IPM 的结构，或者是否存在不遵循 IPM 结构的最佳情况 IPMS 经典的归并排序
我一直在尝试一种 IPM，在最坏的情况下可能会出现这种情况 （对于长度为 N 的 S）需要 ~ 4N/3 次比较和 8N/3 值副本。
但是我不知道这有多好#1 （即，如果低于当前的技术水平，请立即结束工作）， 即使它很好，是否会对最好的 IPMS 产生影响。
看起来 O(N log N) 是 IPM 的常见最坏情况。
Wiki 有一篇关于块合并排序的文章：
https://en.wikipedia.org/wiki/Block_sort
最近在 2023 年 3 月就已经开始研究和开发块合并排序的优化实现，有些代码超过 1000 行。