如何在Scala中編寫'通用'mergesort？

Question

這是我到目前爲止有：

def mergesort[T <: Ordered[T]](elements : List[T]) : List[T] = { 
    def merge(first : List[T], second : List[T]) : List[T] = (first, second) match { 
     case (Nil, _) => second 
     case (_, Nil) => first 
     case (x :: xs, y :: ys) => if (x < y) x :: merge(xs, second) else y :: merge(first, ys) 
    } 

    if (elements.isEmpty) Nil 
    else { 
     val length = elements.length 
     val (firstHalf, secondHalf) = elements.splitAt(length/2) 

     merge(mergesort(firstHalf), mergesort(secondHalf)) 
    } 
    } 

我遇到的問題是，這種失敗

mergesort(List(1, 3, 6, 3, 1, 0)) 

error: inferred type arguments [Int] do not conform to method mergesort's type parameter bounds [T <: Ordered[T]] 
     mergesort(List(1, 3, 6, 3, 1, 0)) 
    ^

有什麼辦法，使這項工作被下令所有類型？我雖然斯卡拉會有某種隱式轉換爲'富'整數類型，我認爲會有Ordered特質。

Answer 1

你需要的是一個視圖綁定def mergesort[T <% Ordered[T]]。看到這個問題的答案：Generic method to return first of two values。

這將現在complie，但你有你的算法中的一些錯誤，在splitAt行給你一個stackoverflow錯誤。