How to write a 'generic' mergesort in Scala?

Question

Here is what I have so far :

  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))
    }
  }

The problem I'm having is that this fails

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))
       ^

Is there any way to make this work for all types which are ordered? I though Scala would have some sort of implicit conversion to a 'rich' integer type, which I assumed would have the Ordered trait.

See some tips here: http://stackoverflow.com/questions/6929637/selection-sort-generic-type-implementation — huynhjl, Mar 24 '12 at 01:34

score 2 · Accepted Answer · edited May 23 '17 at 12:11

2

What you need is a view bound def mergesort[T <% Ordered[T]]. See answers to this question: Generic method to return first of two values.

This will now complie but you have some bugs in your algorithm giving you a stackoverflow error in the splitAt line.

edited May 23 '17 at 12:11

Community

1
1

answered Mar 24 '12 at 02:46

Luigi Plinge

50,650
20
113
180

How to write a 'generic' mergesort in Scala?

1 Answers1