归并排序

MergeSort.scala

package data

/**
 * MergeSort
 * User: flower
 * Date: 2010-10-18
 * Time: 19:27:14
 */
import java.util.Date

object MergeSort {
	
  type T[X] = Traversable[X]

  def mergeSort[X <% Ordered[X]](list: T[X]): T[X] = {

    def split(list: T[X]): (T[X], T[X]) = {
      list.splitAt(list.size >> 1)
    }

    def merge(left: T[X], right: T[X]): T[X] = {

      var (l, r) = (left, right)

      var result = List.empty[X]
      while (l.size > 0 || r.size > 0) {
        if (l.size == 0) {
          result = result ++ r
          return result
        }
        else if (r.size == 0) {
          result = result ++ l
          return result
        }

        val lh = l.head
        val rh = r.head
        if (lh < rh) {
          l = l drop 1
          result = result :+ lh
        } else {
          r = r drop 1
          result = result :+ rh
        }
      }
      result
    }


    if (list.size < 2)
      return list

    val (left, right) = split(list);

    merge(mergeSort(left), mergeSort(right))
  }


  case class Item(val priority: Int) extends Ordered[Item] {
    override def compare(that: Item) = {
      this.priority - that.priority
    }
    //override def toString = "[Item %d]" format priority
  }


  def main(arg: Array[String]): Unit = {

    val rd = new util.Random;
    val arr: Array[Int] = Array.fill(100)(rd.nextInt(3000));

    Console println arr.toList
    Console println arr.length
    Console.println(System.nanoTime / 1000000000.0);
    Console println mergeSort(arr)
    Console.println(System.nanoTime / 1000000000.0);
  }

}