与最小比较排序

Question

给一个策略，以四个不同的整数 A，B，C，d的增加以便进行排序一个，B，C的任何排列所需的成对比较的数目最小化排序，d

我认为有4个整数，所以4！= 24，2^5> 24，所以我们至少需要5次比较。 但我应该在这里使用什么策略？ 我可以使用计数排序或BBST或其他任何东西来最小化它。

Answer 1

A sorting network将使用5个比较/交换对4个数字排序，其中两个比较/交换可以在硬件类型实现中并行执行。如果两个潜在的并行比较/交换使用4个单独的寄存器完成，那么有些处理器可能会通过至少重叠比较交换来优化这一点。