我正在寻找一种有效的算法来执行以下操作：给定一个由N个项目组成的数组，对其进行排序，使项目成为m个相等的组，其中每个组都是未排序的，但组之间是排序的（一组中的所有元素都小于下一组的任何元素）。
最简单的方法是对整个数组进行排序。但这是低效的，尤其是如果组的数量远小于项目的总数（例如，将一百万个项目分为5组）。
目前，我已经决定使用快速选择算法（特别是Floyd-Rivest变体），将数组排序为2个未排序的组，然后应用M-1次。一个显著的改进可能是将分而治之的方法应用于快速选择，首先将数组排序为两组，然后对每一半进行排序，等等，直到我们有M组。无序部分排序问题的一种推广。
但我有一种直觉，也许有一种更简单、更有效的方法来解决这个问题。我缺什么了吗？有什么想法吗？我需要它来提高我的RBush JavaScript库（一个高效的R*树实现）中的大容量插入性能。
这是对问题的重述。您需要同时找到M-1个排序的元素，并使用它们将数组划分为M个未排序的组。
我建议从标准的快速选择开始，选择接近中位数的随机枢轴（做随机子样本技巧来估计），对于每种情况，将数组划分为2，也将需要查找的排序元素列表划分为2。继续这样做，直到你达到在当前组中可以找到排名元素的水平。然后切换到快速选择的Floyd-Rivest变体，以实际找到该元素，并将当前组拆分为2。然后从快速选择中返回，您可以轻松地将所需的M个组拼凑在一起。
这种方法的预期运行时间为O(N log(M))，具有相当好的常数。我怀疑比这更好的做法是否可行。