プリミティブ型のソートでは最悪計算時間に注意する

Java11にはさまざまなソートAPIが用意されていますが、ソートアルゴリズムとして、プリミティブ型のソートにはDual Pivot Quick Sortが、参照型のソートにはTimsortがそれぞれ採用されています (以下はjava.util.Arraysより抜粋したもの)

Arrays.java

public class Arrays {
    public static void sort(int[] a) {
        DualPivotQuicksort.sort(a, 0, a.length - 1, null, 0, 0);
    }

    public static void sort(Object[] a) {
        if (LegacyMergeSort.userRequested)
            legacyMergeSort(a);
        else
            ComparableTimSort.sort(a, 0, a.length, null, 0, 0);
    }
}

詳細は英語版Wikipediaやニコニコ大百科の記事などを見てほしいのですが、Timsortはざっくりいってしまうとマージソートの改良版みたいなもので、平均計算時間・最悪計算時間ともに$O(nlog{n})$です。一方、Dual Pivot Quick Sortは改良版とはいえもともとはクイックソートなので、平均計算時間はTimsortと同じ$O(nlog{n})$ですが、最悪計算時間は$O(n^2)$になります。つまり、Java11でプリミティブ型のソートを行う場合は$O(n^2)$になる可能性があることに注意する必要があるということです。

実をいうと、プリミティブ型のソートの最悪計算時間が$O(n^2)$だということはJavaDocにもきっちり書かれていることで、たとえば以下はArrays.sortからの抜粋になります。

Implementation note: The sorting algorithm is a Dual-Pivot Quicksortby Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithmoffers O(n log(n)) performance on many data sets that cause otherquicksorts to degrade to quadratic performance, and is typicallyfaster than traditional (one-pivot) Quicksort implementations.

要は知らなかったではすまされないということですね…

プリミティブ型のソートの計算時間が$O(n^2)$になるのは天文学的な確率というか、現実的にはJavaを意図的に攻撃するような場合にしか起きないのですが、例えばCodeforcesにはHackという、他人のソースコードが正解できないようなテストケースを考えて提出できる仕組みがあり、このHackでは狙われる場合があります。Codeforcesユーザの中ではこれをAnti Quick SortとかQuick Sort Killerとかいうそうで、そういうテストケースのジェネレータを公開している人もいます: https://codeforces.com/blog/entry/4827

現実のアプリケーションを作っている現場では、俗に「いじわるテスト」などと称して、ある種のストレステストを行うことがありますが、このときにAnti Quick Sort / Quick Sort Killerを試してみても良いかもしれません。