为什么R语言内置sort函数处理短向量时速度比简易冒泡排序慢？

核心原因有三点：

• R内置sort是通用泛型函数，设计上需要兼容所有可排序的输入类型（数值、字符、因子、逻辑值等），还要支持自定义排序规则、缺失值处理、升降序切换等多种参数，调用前要做大量的参数校验、输入合法性检查工作，这部分是固定开销，和输入向量长度无关。
• 内置sort的核心逻辑是C语言实现的，R调用C函数本身有固定的调用开销，对于长度只有2、3的向量来说，这部分开销远大于排序本身的计算耗时。
• 你写的简易冒泡排序是专门针对数值向量的极简实现，没有任何额外校验逻辑，而且全程在R层运行没有跨语言调用开销，在n极小的时候，O(n²)的排序耗时远低于内置sort的固定开销，所以看起来更快。

从你给出的基准测试结果也能印证这一点：当向量长度上升到20的时候，冒泡排序的中位数耗时已经达到88微秒，远高于内置sort的40.4微秒，这是因为冒泡排序O(n²)的时间复杂度劣势随着n增大快速显现，而内置sort的固定开销占比会随着n增大快速降低，O(nlogn)的复杂度优势就会体现出来。

bubblesort <- function(x) {
  i <- length(x)
  while (i>1) {
    j <- 1
    while (j<i) {
      if (x[j]>x[j+1])
        x[j+0:1] <- x[j+1:0]
      j <- j + 1
    }
    i <- i - 1
  }
  x
}
x <- runif(10)
bubblesort(x)
#>  [1] 0.07146454 0.20584236 0.21178417 0.54820837 0.60373045 0.71108993
#>  [7] 0.72068104 0.91850898 0.96016281 0.98805395
sort(x)
#>  [1] 0.07146454 0.20584236 0.21178417 0.54820837 0.60373045 0.71108993
#>  [7] 0.72068104 0.91850898 0.96016281 0.98805395
microbenchmark::microbenchmark(
  sort(runif(2)),
  bubblesort(runif(2)),
  sort(runif(3)),
  bubblesort(runif(3)),
  sort(runif(10)),
  bubblesort(runif(10)),
  sort(runif(20)),
  bubblesort(runif(20))
)
#> Unit: microseconds
#>                   expr    min      lq     mean  median      uq     max neval
#>         sort(runif(2)) 30.228 35.6835 44.62655 38.9970 44.0060 191.712   100
#>   bubblesort(runif(2))  2.203  3.2455  4.46545  4.1930  5.2440  10.289   100
#>         sort(runif(3)) 32.843 36.4460 42.65150 38.7410 41.2360 152.067   100
#>   bubblesort(runif(3))  2.555  4.6670  6.89911  5.6525  7.3650  73.671   100
#>        sort(runif(10)) 31.717 37.6945 42.81501 39.0330 43.6345 107.488   100
#>  bubblesort(runif(10)) 13.561 21.6865 27.18694 25.7375 28.5140  97.375   100
#>        sort(runif(20)) 31.761 38.2905 46.33787 40.3975 43.9200 177.757   100
#>  bubblesort(runif(20)) 54.018 78.3025 91.85322 88.0000 99.3935 266.090   100

内容的提问来源于stack exchange，提问作者Jarle Tufto