在JavaScript中（某種程度上適用於其他地方），您不知道代碼在哪個目標上運行，是否有一種方法可以檢測底層排序算法（Array.sort）是否穩定，只知道它如下the specification？是否有黑盒方法來檢測排序算法是否穩定？
我可以在webkit (1)(2)中找到2個測試，但這些測試有多可靠？ （可以用PCP來完成這項檢查嗎？）我正在尋找一種數學上可行的解決方案。
這是一個棘手的問題，因爲更高級的排序算法可以根據源數組長度（如Timsort）更改子算法。我一直困惑，因爲我運行的每個測試都表明谷歌瀏覽器穩定，但我所見過的所有文檔都表示它不穩定（the source會告訴你爲什麼）。
（通常情況下，我用this strategy讓我的各種各樣的穩定;它具有體積小，但有時noticable性能的影響）
的源代碼在各種實現排序：運行一個小的內部測試，檢查？你可以使用「按排名打牌，然後用維基百科的例子」來檢查穩定性。
請參見：https://en.wikipedia.org/wiki/Sorting_algorithm#Stability
我不知道你需要多少卡檢查穩定性 - 也許5左右？
數學上的聲音，呃？這將要求算法中的每條路徑都被證明是穩定的 - 以及它們的每個組合。對於任何可能的數據。
確實存在這樣的算法 - 但它們很可能是爲了滿足這個要求而設計的。所以如果是這樣，它可能會說它在某個地方。
至於一個證明類似的測試，這可能屬於類似的問題作爲一個停機問題。
不確定是否需要調用暫停問題，但應該清楚的是超指數搜索對於給定輸入大小涵蓋*全部*可能性是必需的 – 2013-05-15 21:04:39
黑箱測試不能被用來確定程序符合任何標準，除非你可以測試相關的標準，所有可能的輸入。一個黑匣子可以自由地擁有一個將輸入映射到輸出的查找表（請參閱Pentium FDIV bug以瞭解真實世界的查找表錯誤），因此您無法確定您的測試是否排除了某些其他輸入觸發違規的可能性。
爲什麼冒這個險？對於大多數合理的數據集，合併排序的JavaScript實現應該足夠快。挑選一對夫婦並進行基準測試並使用最好的一個。
你只能在概率上做出這樣的決定：例如，我可以定義一個排序算法'S'，輸入'I'。通常情況下，'S'將實際的分類工作排除在某種穩定的排序算法'T'上，*但*當'I'等於某個特殊值'I''時，它使用非穩定排序'U'。你永遠不會證明'S'是非穩定的，除非你運氣好，恰巧通過'I''作爲輸入。更現實的是，也許'S'使用穩定的排序，除非'I'很長。同樣，如果您測試適當長的輸入，您只會觀察到非穩定排序。 – apsillers 2013-05-15 20:43:42
如果規範說明它不穩定，那並不意味着您可以期望在排序數組時排序項目，而是您不能依賴它;沒有承諾。 （當前）實現恰好穩定並不意味着它將永遠是或者所有平臺上的chrome運行。 – frozenkoi 2013-05-15 20:47:40
我同意@MarZab這是一個暫停問題的問題。如果您將其標記爲[計算機科學]和/或[計算機科學理論]，您可能會看到更多的關注。 – apsillers 2013-05-15 20:47:45