最小比较排序

Question

给出一个策略，将四个不同的整数a，b，c，d按升序排序，从而最小化排序a，b，c，d的任何排列所需的成对比较的次数

我认为有4个整数，所以4!=24，2^5>24，所以我们至少需要5个比较。但是我应该在这里使用什么策略呢？我可以使用Counting sort或BBST或任何其他方法来最小化它吗？

Answer 1

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