這篇文章會用 TDD 手刻 mySorted、mySortedDescending、mySortedBy、mySortedByDescending，搞懂 Kotlin 排序操作的泛型約束和底層機制。排序篇從這裡開始

Kotlin ↔ C# 對照表

Comparable 介面

排序的前提是「東西之間能比大小」。在 Kotlin 裡，這靠 Comparable<T> 介面

public interface Comparable<in T> {
    public operator fun compareTo(other: T): Int
}

compareTo 回傳值的規則：負數代表 this < other，零代表相等，正數代表 this > other

Int、String、Double 這些型別都實作了 Comparable，所以可以直接拿來排序。自訂的 data class(像我們的 Employee)沒有實作 Comparable，不能直接用 sorted()，但可以用 sortedBy 指定「拿什麼欄位來比」

為什麼還需要 Comparator？

Comparable 只解決一半問題：型別內建一種「自然順序」。但同一個型別常常要用不同方式排，Employee 可能要按薪水排，也可能要按年齡或入職日期排，這時候型別內建的單一順序就不夠用了

另一半由 Comparator 補上：比較規則由外部提供，呼叫排序時才決定，同一個型別想怎麼比就怎麼比。Java 1.2 引入 Collections Framework 時就同時設計了這兩個介面，這不是設計失誤。它們對應兩個正交需求，一個是「型別內建的自然順序」(Comparable)，另一個是「呼叫情境臨時決定的規則」(Comparator)

day 16 會手刻 mySortedWith，把 Comparator 的組合方式完整講清楚

sorted vs sort — 不可變 vs 可變

Kotlin 的命名有一個簡單的規則

sorted() — 回傳新的 List，原集合不動。過去分詞(sorted)暗示「已排序的副本」

sort() — 原地排序，修改 MutableList 本身。動詞原形(sort)暗示「執行排序動作」

val numbers = mutableListOf(3, 1, 2)

// sorted() 回傳新 List
val newList = numbers.sorted()
println(newList)    // [1, 2, 3]
println(numbers)    // [3, 1, 2]  原始不動

// sort() 原地修改
numbers.sort()
println(numbers)    // [1, 2, 3]  被改了

Collection 操作幾乎都遵循這套命名慣例。reversed() 回傳新 List，reverse() 原地反轉。看到過去分詞就知道不會改原集合

我們這篇手刻的是 sorted 系列，都回傳新 List

TDD 實作 mySorted 與 mySortedDescending

Red：先寫測試

@Test
fun `sorted integers in natural order`() {
    val numbers = listOf(5, 3, 1, 4, 2)
    val result = numbers.mySorted()
    assertEquals(listOf(1, 2, 3, 4, 5), result)
}

@Test
fun `sorted strings in natural order`() {
    val words = listOf("banana", "apple", "cherry")
    val result = words.mySorted()
    assertEquals(listOf("apple", "banana", "cherry"), result)
}

@Test
fun `sorted does not modify original list`() {
    val numbers = listOf(3, 1, 2)
    val result = numbers.mySorted()
    assertEquals(listOf(1, 2, 3), result)
    assertEquals(listOf(3, 1, 2), numbers)
}

@Test
fun `sorted empty list returns empty list`() {
    assertEquals(emptyList<Int>(), emptyList<Int>().mySorted())
}

@Test
fun `sorted single element list`() {
    assertEquals(listOf(42), listOf(42).mySorted())
}

@Test
fun `sortedDescending integers in reverse natural order`() {
    val numbers = listOf(5, 3, 1, 4, 2)
    assertEquals(listOf(5, 4, 3, 2, 1), numbers.mySortedDescending())
}

@Test
fun `sortedDescending employee salaries`() {
    val salaries = employees.map { it.salary }
    val result = salaries.mySortedDescending()
    assertEquals(92_000, result.first())
    assertEquals(55_000, result.last())
}

@Test
fun `sortedDescending does not modify original list`() {
    val numbers = listOf(3, 1, 2)
    assertEquals(listOf(3, 2, 1), numbers.mySortedDescending())
    assertEquals(listOf(3, 1, 2), numbers)
}

第三個測試很重要，它確認 mySorted() 回傳新 List，不會動到原集合。接著兩個是邊界案例：空集合和單一元素都該安全通過，不用排也不會炸

薪水那個測試繞了一手 employees.map { it.salary }，才用得到系列共用的資料集。原因是 Employee 沒有實作 Comparable，直接寫 employees.mySorted() 會被泛型約束擋在編譯期

// employees.mySorted()
// 編譯不過：Candidate 'fun <T : Comparable<T>> Iterable<T>.mySorted(): List<T>'
// is inapplicable because of a receiver type mismatch.

訊息講的是 receiver 不匹配，不是約束沒滿足，因為 T 就是從 receiver 推出來的。推成 Employee 之後不滿足 Comparable<Employee> 這個上界，這個候選就整個被剔掉了

null 行為也是同一道關卡擋下來的。T : Comparable<T> 讓 List<Int?> 這種含 null 的集合一樣編譯不過，所以 mySorted 不需要為 null 補 runtime 測試，型別系統已經把這條路堵死了

最後那個「不改原集合」在 mySortedDescending 這邊也測了一次。降冪走的是另一條實作路徑，不是把升冪的結果反轉回來，所以得各自確認過才算數。差在哪，等一下寫實作就會看到

Green：最小實作

fun <T : Comparable<T>> Iterable<T>.mySorted(): List<T> {
    val list = this.toMutableList()
    list.sort()
    return list
}

三行搞定。toMutableList() 複製一份，sort() 原地排序這份副本，最後回傳

泛型約束 T : Comparable<T> 是關鍵。沒有這個約束，編譯器不知道 T 能不能比大小，sort() 就叫不了。Red 階段那個編譯不過的註解，擋下來的就是它

mySortedDescending 一併補上，讓 Red 階段後面那三個測試轉綠

fun <T : Comparable<T>> Iterable<T>.mySortedDescending(): List<T> {
    val list = this.toMutableList()
    list.sortWith(compareByDescending { it })
    return list
}

sortWith 接受一個 Comparator，compareByDescending { it } 產生一個反向的 Comparator。day 16 會深入講 Comparator 的組合技

Refactor：往 stdlib 的寫法靠近

Green 的三行可以用 apply 縮成一行

fun <T : Comparable<T>> Iterable<T>.mySorted(): List<T> {
    return this.toMutableList().apply { sort() }
}

行為完全一樣：toMutableList() 複製、sort() 原地排序、apply 回傳排序完的那份副本。這也是 stdlib sorted() 在一般 Iterable 路徑上的寫法

mySortedDescending 用同一招縮成一行

fun <T : Comparable<T>> Iterable<T>.mySortedDescending(): List<T> {
    return this.toMutableList().apply { sortWith(compareByDescending { it }) }
}

mySortedDescending 就先停在自己組 Comparator 的這個版本，等 day 16 手刻完 mySortedWith 還能再簡化一次。stdlib 用的又是另一套寫法，等一下比較原始碼時一起看

TDD 實作 mySortedBy 與 mySortedByDescending

Red：先寫測試

@Test
fun `sortedBy employee salary`() {
    val result = employees.mySortedBy { it.salary }
    assertEquals("Frank", result[0].name)
    assertEquals("Eve", result[1].name)
    assertEquals("Grace", result.last().name)
}

@Test
fun `sortedBy employee name`() {
    val result = employees.mySortedBy { it.name }
    assertEquals("Alice", result[0].name)
    assertEquals("Grace", result.last().name)
}

@Test
fun `sortedBy string length`() {
    val words = listOf("banana", "fig", "apple", "kiwi")
    val result = words.mySortedBy { it.length }
    assertEquals("fig", result[0])
    assertEquals("banana", result.last())
}

@Test
fun `sortedBy puts null selector results first`() {
    val words = listOf("banana", null, "apple")
    val result = words.mySortedBy { it }
    assertEquals(listOf(null, "apple", "banana"), result)
}

@Test
fun `sortedByDescending employee salary`() {
    val result = employees.mySortedByDescending { it.salary }
    assertEquals("Grace", result[0].name)
    assertEquals("Frank", result.last().name)
}

@Test
fun `sortedByDescending puts null selector results last`() {
    val words = listOf("banana", null, "apple")
    assertEquals(listOf("banana", "apple", null), words.mySortedByDescending { it })
}

sortedBy 接受一個 Lambda (T) -> R，用 R 的大小來決定排序。Employee 本身不能比大小，但 it.salary(Int) 和 it.name(String) 可以

第三個測試拿字串按長度排序，展示 T 和 R 可以是不同型別

兩個 null 測試放在一起看，會冒出一件不太對稱的事：selector 都允許回傳 null，但 mySortedBy 的 null 排最前面，mySortedByDescending 的 null 卻排最後面。這不是隨便訂的，等一下看實作就知道為什麼

Green：最小實作

inline fun <T, R : Comparable<R>> Iterable<T>.mySortedBy(
    crossinline selector: (T) -> R?
): List<T> {
    return this.toMutableList().apply { sortWith(compareBy(selector)) }
}

泛型約束從 T : Comparable<T> 變成了 R : Comparable<R>。T 本身不需要能比大小，只要 Lambda 回傳的 R 能比就行

compareBy(selector) 是 Kotlin 標準函式庫提供的工具，它把 (T) -> R? 轉成 Comparator<T>。sortWith 再拿這個 Comparator 去排序

注意 selector 的型別是 (T) -> R?，允許回傳 null。compareBy 預設把 null 當成最小值，所以升冪排序時 null 排在最前面

crossinline 的理由是執行位置。selector 最後會被包進 compareBy 產生的 Comparator 物件、在它的 compare 裡執行，不是在 mySortedBy 的呼叫框架裡展開。既然執行時外層函式那個框架可能早就不在了，非局部 return 就無處可回，所以編譯器要求標 crossinline 把它擋掉

拿掉 crossinline 試試就知道，編譯器會直接說 Cannot inline 'selector: (T) -> R?' here: it might contain non-local returns. Add 'crossinline' modifier to parameter declaration 'selector: (T) -> R?'.

apply 的寫法讓整個操作一行搞定：建立 MutableList → 排序 → 回傳自己。這裡先記一個最小定義就夠用：x.apply { ... } 會在 Lambda 裡把 x 當成 this，執行完回傳 x 本身而不是 Lambda 的結果，所以很適合「建好物件、調整一下、直接交出去」這種寫法。day 32 會完整講 Scope Functions 五兄弟的差異

mySortedByDescending 的版本如下

inline fun <T, R : Comparable<R>> Iterable<T>.mySortedByDescending(
    crossinline selector: (T) -> R?
): List<T> {
    return this.toMutableList().apply { sortWith(compareByDescending(selector)) }
}

把 compareBy 換成 compareByDescending，其他完全一樣

Red 那個 null 位置翻面的謎底也在這裡。compareByDescending(selector) 內部做的是 compareValues(selector(b), selector(a))，兩個參數對調了，「null 最小」的語意跟著翻面，最小值就跑到最後面去

Refactor：往 stdlib 的寫法靠近

Green 的寫法已經和 stdlib 幾乎重疊，唯一差別是 stdlib 把「複製再排序」這段委託給 sortedWith。和前面的 mySortedDescending 一樣停在這裡，等 day 16 手刻 mySortedWith 之後，mySortedBy 就能改寫成一行 mySortedWith(compareBy(selector))，mySortedByDescending 換成 compareByDescending 同理

與 stdlib 原始碼比較

原始碼位置：kotlin.collections 的 _Collections.kt

stdlib 的 sortedBy 長這樣

public inline fun <T, R : Comparable<R>> Iterable<T>.sortedBy(
    crossinline selector: (T) -> R?
): List<T> {
    return sortedWith(compareBy(selector))
}

差異在 stdlib 呼叫的是 sortedWith，而不是直接操作 MutableList。sortedWith 裡面做的事和我們一樣，就是 toMutableList() + sortWith(comparator)

public fun <T> Iterable<T>.sortedWith(comparator: Comparator<in T>): List<T> {
    if (this is Collection) {
        if (size <= 1) return this.toList()
        @Suppress("UNCHECKED_CAST")
        return (toTypedArray<Any?>() as Array<T>).apply { sortWith(comparator) }.asList()
    }
    return toMutableList().apply { sortWith(comparator) }
}

stdlib 多了一個最佳化：如果是 Collection 且元素不超過 1 個，直接回傳不排序。另外它用 toTypedArray() 轉成陣列再排，因為陣列排序在 JVM 上比 List 排序快一點。寫成 toTypedArray<Any?>() 再強制轉型，是因為 sortedWith 不是 inline 函式，拿不到 reified 的 T，只能先建 Array<Any?> 再 cast 回 Array<T>

sortedDescending 那邊還有一個差異

public fun <T : Comparable<T>> Iterable<T>.sortedDescending(): List<T> {
    return sortedWith(reverseOrder())
}

我們手刻的版本是現場組一個反向 Comparator(compareByDescending { it })，stdlib 拿的是 reverseOrder() 這個現成的。差別在物件配置。compareByDescending { it } 每呼叫一次就 new 一個 Comparator 出來，reverseOrder() 直接回傳現成的單例。至於 { it }，它被內聯進那個 Comparator 的 compare 裡，不會再多生一個 Lambda 物件。行為一樣，stdlib 的寫法更省

最底層都是呼叫 Java 的 Arrays.sort()，用的是 TimSort。Kotlin 不自己重寫一套排序邏輯，直接站在 Java 的肩膀上

小結

排序操作的泛型約束和前幾篇不太一樣。sorted() 要求 T : Comparable<T>，sortedBy 放寬到只要 R : Comparable<R>。底層不用自己重寫一套排序邏輯，交給 Java 的 TimSort 就好

crossinline 是這篇新冒出來的修飾詞。因為 Lambda 會被傳進排序器裡反覆呼叫，不是直接在外層函式裡 inline 展開，所以需要 crossinline 來限制非局部 return

還有一個容易踩到的：sortedBy 的 null 排在最前面，sortedByDescending 的 null 卻跑到最後面。compareByDescending 把比較的兩個參數對調了，「null 最小」的語意跟著翻面

下一篇講多欄位排序。如果要按部門排完再按薪水排呢？sortedWith + compareBy + thenBy 的 Comparator 組合技登場

參考資料

• Kotlin 官方文件：Ordering
• Kotlin 官方文件：Inline functions(crossinline)
• Kotlin 官方文件：Scope functions
• Kotlin API：sorted
• Kotlin API：sortedDescending
• Kotlin API：sortedBy
• Kotlin API：sortedByDescending
• Kotlin API：sortedWith
• Kotlin API：sort
• Kotlin API：compareBy
• Kotlin API：compareByDescending
• Kotlin API：reverseOrder
• Kotlin API：Comparable
• Kotlin API：Comparator
• Kotlin API：apply
• Kotlin stdlib 原始碼：_Collections.kt
• Kotlin stdlib 原始碼：Comparisons.kt
• Java API：Arrays.sort(TimSort)
• .NET API：Enumerable.OrderBy
• .NET API：Enumerable.OrderByDescending
• .NET API：IComparable 介面
• .NET API：IComparer 介面
• C# 官方文件：排序資料

同步刊登於 Blog

圖片來源：AI 產生