爲什麼OCaml有兩個排序函數：List.sort和List.stable_sort？

Question

這裏的DOC：

---

val sort : ('a -> 'a -> int) -> 'a list -> 'a list 

排序中根據比較函數遞增的順序列表。如果比較函數的參數比較爲相等，則比較函數必須返回0;如果第一個較大，則返回正整數;如果第一個較小，則返回負整數（有關完整規範，請參閱Array.sort）。例如，比較是一個合適的比較函數。結果列表按升序排列。 List.sort保證運行在恆定的堆空間（除了結果列表的大小）和對數棧空間。

當前實現使用合併排序。它運行在不斷的堆空間和對數棧空間中。

val stable_sort : ('a -> 'a -> int) -> 'a list -> 'a list 

同List.sort，但the sorting algorithm is guaranteed to be stable（即該比較相等的元素被保持在它們的原始順序）。

當前實現使用合併排序。它運行在不斷的堆空間和對數棧空間中。

---

我以爲merge sort反正是穩定的吧？

OCaml如何產生non-stable merge排序？

在non-statble merge sort版本中，速度更快嗎？

Answer 1

合併排序是穩定的，但排序使用合併排序的事實不是其合約的一部分。請注意，它只表示「當前實施使用...」。不能保證將來它會繼續使用合併排序，因此如果在代碼中使用List.sort，即使它在當前實現中可能穩定，也不能保證排序穩定。

只要每個需要穩定排序的代碼使用stable_sort，如果Ocaml的未來版本（或替代實現）切換爲sort的不穩定算法，則不會有代碼破壞。

Answer 2

您需要將定義與實現分開。實施者保留改變實施的權利，並且對功能如何被定義爲行爲而言是令人欽佩的和清楚的。