Go の sort.Slice でソートできない

現象

sort.Slice の第二引数の結果を、第一引数のスライス以外から算出すると、ソートが期待通りに動かない。

    sort.Slice(dates, func(i, j int) bool {
        return times[i].Before(times[j])
    })

具体例

文字列の日付のスライスをソートを行いたいとします。
ソート処理には sort.Slice を使用します。

    dates := []string{
        "2022-05-02",
        "2022-05-03",
        "2022-05-01",
    }
    
    times := make([]time.Time, len(dates))
    for i, date := range dates {
        d, err := time.Parse("2006-01-02", date)
        if err != nil {
            return err
        }
        
        times[i] = d
    }
    
    sort.Slice(dates, func(i, j int) bool {
        return times[i].Before(times[j])
    })

しかし、この実装ではソートが上手くいきません。

    fmt.Println(dates) // [2022-05-02 2022-05-01 2022-05-03]

一体なぜでしょうか？

また、少し変な実装に感じるかもしれませんが、その実装に至るまでの仮定は次のセクションで書きます。
急いでいる人は省いて構いません。

具体例までの過程

日付をソートしたいのでまず、雛形を考えてみます。

    dates := []string{
        "2022-05-02",
        "2022-05-03",
        "2022-05-01",
    }
    
    sort.Slice(dates, func(i, j int) bool {
        // TODO write here.
    })

文字列のまま比較できるのかもしれませんが、仕様的に保証されていない気がするので避けます。
time.Time 型に変換してから比較します。

    dates := []string{
        "2022-05-02",
        "2022-05-03",
        "2022-05-01",
    }
    
    sort.Slice(dates, func(i, j int) bool {
        d1, err := time.Parse("2006-01-02", dates[i])
        if err != nil {
            return err // not bool
        }
        // あれ、 err をどうしよう、、、
        // bool ではないから直接 return できない
    })

素直に実装すると、err のハンドリングで少し違和感を覚えます。
この err はそのまま return できません。

スコープ外に err 変数を定義し、再代入する形だとかなり冗長なコードになります。

そこで以下のように実装しました。
time.Time への変換を sort.Slice の第二引数の func(i, j int) bool 関数の外側で行います。
内側で行ってしまうと、 第二引数の関数が bool しか返せず、エラーハンドリングが冗長になるためです。

    dates := []string{
        "2022-05-02",
        "2022-05-03",
        "2022-05-01",
        "2022-06-01",
    }
    
    times := make([]time.Time, len(dates))
    for i, date := range dates {
        d, err := time.Parse("2006-01-02", date)
        if err != nil {
            return nil
        }
        
        times[i] = d
    }
    
    sort.Slice(dates, func(i, j int) bool {
        return times[i].Before(times[j])
    })

原因

sort.Slice の第二引数の結果の材料を、第一引数のスライス以外から取得しているためです。

sort.Sclie は複数回に渡り第二引数の関数を呼び出していきますが、その都度第一引数のスライスの順番を入れ替えています。
第二引数の関数の結果は、第一引数のスライスから算出する前提 の設計になっています。

そのため、第二引数の関数の結果を、第一引数のスライス以外から処理すると意図しない挙動になります。

解決策

sort.Slice の第二引数の結果を、第一引数のスライスから算出します。
第二引数の関数内でエラーが発生する場合、冗長ですが第二引数の関数内で発生させ、スコープの外側に渡しましょう。

この方法はかなり冗長です。
可能ならばソートせずに済む方法を考え、回避することをおすすめします。

具体例

冒頭で示した具体例は、正しく書き直すと次のとおりになります。

    dates := []string{
        "2022-05-02",
        "2022-05-03",
        "2022-05-01",
    }
    
    var err error
    sort.Slice(dates, func(i, j int) bool {
        if err != nil {
            return false
        }
        
        d1, e := time.Parse("2006-01-02", dates[i])
        if e != nil {
            err = e
            return false
        }
        d2, e := time.Parse("2006-01-02", dates[j])
        if e != nil {
            err = e
            return false
        }

        return d1.Before(d2)
    })
    if err != nil {
        return err
    }

思わずここまでやるかと感じるほどに、とても面倒です。
この実装だと期待通りの動作を行います。

終わりに

sort.Slice への理解不足が原因ですが、第二引数と第一引数の関係に気づくまでに多くの時間をかけてしまいました。
また、公式ドキュメントや他の記事を読んでも sort.Slice 関数の詳しい解説は皆無なように感じます。

もしかしたら CS を取得されていたりアルゴリズムを理解されている方には当たり前なのかもしれませんが、
この機会に sort.Slice がなぜそのような設計になっているのか、そのような仕組みになっているのかを理解しようと思います。