Skip to content

Instantly share code, notes, and snippets.

@melpomene
Created October 24, 2012 20:18
Show Gist options
  • Save melpomene/3948590 to your computer and use it in GitHub Desktop.
Save melpomene/3948590 to your computer and use it in GitHub Desktop.
Merge-sort in Scala
import scala.util.Random
import scala.Math.min
import scala.runtime.ScalaRunTime._
class MergeSort(list: Array[Int]) {
def sort(): Array[Int] = {
reqSort(list)
}
def merge(v1: Array[Int], v2: Array[Int]): Array[Int] = {
var res: Array[Int] = Array()
var sorted = false
var i, j = 0
while (!sorted) {
if (v1(i) < v2(j)) {
res = res :+ v1(i)
i += 1
} else {
res = res :+ v2(j)
j += 1
}
if (i >= v1.length) {
res = res ++ v2.drop(j)
sorted = true
} else if (j >= v2.length) {
res = res ++ v1.drop(i)
sorted = true
}
}
res
}
def reqSort(v: Array[Int]): Array[Int] = {
v match {
case Array(_) => v
case Array(x,y) => {
if (x < y){
v
} else {
y +: Array(x)
}
}
case _ => {
val (v1, v2) = v.splitAt(v.length / 2)
merge(reqSort(v1), reqSort(v2))
}
}
}
}
object Main {
def main(args: Array[String]) {
val r = new Random()
val list = (1 to 10) map { _ => r.nextInt() }
println("Done Generating list")
//println(stringOf(list))
println("Sorting with merge sort")
val s = new MergeSort(list.toArray[Int])
println("Sorting is complete")
println(stringOf(s.sort()))
println("Bye bye")
}
}
@melpomene
Copy link
Author

Thanks for feedback! Very aware of the java-esque style in the code, though about even commenting on it.
Will do a clean up of the code when I am back from Berlin!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment