Skip to content

Instantly share code, notes, and snippets.

@taintech
Created March 10, 2018 13:25
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save taintech/ca73bbaae6481174ba6933ca4c6f186d to your computer and use it in GitHub Desktop.
Save taintech/ca73bbaae6481174ba6933ca4c6f186d to your computer and use it in GitHub Desktop.
Scala merge sort implementation
import scala.annotation.tailrec
object sortings {
//p <= q < r
def merge(ar: Array[Int], p: Int, q: Int, r: Int): Array[Int] = {
val x = q - p + 1
val left = new Array[Int](x + 1)
Array.copy(ar, p, left, 0, x)
left(left.length - 1) = Int.MaxValue
val y = r - q
val right = new Array[Int](y + 1)
Array.copy(ar, q + 1, right, 0, y)
right(right.length - 1) = Int.MaxValue
@tailrec
def loop(i: Int, li: Int, ri: Int): Unit =
if (i > r) Unit
else {
if (left(li) <= right(ri)) {
ar(i) = left(li)
loop(i + 1, li + 1, ri)
} else {
ar(i) = right(ri)
loop(i + 1, li, ri + 1)
}
}
loop(p, 0, 0)
ar
}
def mergeSort(ar: Array[Int]): Array[Int] = {
def mergeSortLoop(ar: Array[Int], p: Int, r: Int): Unit = {
if (p >= r) Unit
else {
val q = (p + r) / 2
mergeSortLoop(ar, p, q)
mergeSortLoop(ar, q + 1, r)
merge(ar, p, q, r)
}
}
mergeSortLoop(ar, 0, ar.length - 1)
ar
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment