`Vector.splitAt`

splits a vector into two parts at the index you specify. The first part ends just before the element at the given index; the second part starts with the element at the given index. Some examples will help:

### Some Examples

The most obvious use case is bisecting a vector, i.e., splitting it into two (nearly) equal parts. To do that, half the length, and use it as your splitting index:

val xs = Vector(1,2,3,4,5,6) val mid = xs.length / 2 // 3 val (left, right) = xs splitAt mid // left: Vector[Int] = Vector(1, 2, 3) // right: Vector[Int] = Vector(4, 5, 6)

But what happens if your vector contains an **odd** number of elements? No sweat! Because of the way integer division works, the quotient `length ÷ 2` is truncated. In other words, the `left`

vector will always have one less element than the `right`

vector:

val xs = Vector(1,2,3,4,5) val mid = xs.length / 2 // 2 val (left, right) = xs splitAt mid // left: Vector[Int] = Vector(1, 2) // right: Vector[Int] = Vector(3, 4, 5)

Of course, you don’t have to cut the thing in half. You can split it anywhere:

val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 1 // left: Vector[Int] = Vector(1) // right: Vector[Int] = Vector(2, 3, 4, 5)

Or …

val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 4 // left: Vector[Int] = Vector(1, 2, 3, 4) // right: Vector[Int] = Vector(5)

What happens if you split at index 0?

val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 0 // left: Vector[Int] = Vector() // right: Vector[Int] = Vector(1, 2, 3, 4, 5)

Ah, the `left`

vector is empty! That’s because `Vector.splitAt`

**starts** the `right`

vector **at** the given index. There’s nothing before the given index, so the only thing left to return for `left`

is an empty vector.

The reverse happens if you split at the length: The `right`

vector is empty while the `left`

vector contains the entire input vector:

val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 5 // left: Vector[Int] = Vector(1, 2, 3, 4, 5) // right: Vector[Int] = Vector()

But what happens if you try to split at an index **greater** than the length?

val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt 6 // left: Vector[Int] = Vector(1, 2, 3, 4, 5) // right: Vector[Int] = Vector()

Well, that’s interesting. So then, if you split at any index greater than the length of the input vector, the `left`

contains the input vector while the `right`

vector is empty.

You get the reverse if you split on a negative number:

val xs = Vector(1,2,3,4,5) val (left, right) = xs splitAt -1 // left: Vector[Int] = Vector() // right: Vector[Int] = Vector(1, 2, 3, 4, 5)

### Merge Sort with Vector.splitAt

You can use `Vector.splitAt`

in performing a merge sort. `Vector.splitAt`

is, admittedly, a pretty small piece of the puzzle. Merge sort is a divide-and-conquer algorithm, and `Vector.splitAt`

just performs the *divide* part. Nevertheless it comes in handy for that part.

Speaking of which, start by using `Vector.splitAt`

to define a `bisect`

function that splits a vector in half:

def bisect[A](xs: Vector[A]) = { val mid = xs.length / 2 xs splitAt mid }

A merge sort breaks a vector down into single-element (or empty) vectors and then puts them back together, sorting the elements of each block as it combines them. Start with the `merge`

function that puts the blocks back together after you’ve broken them down:

def merge(left: Vector[Int], right: Vector[Int]) = { @tailrec def mergeWith(l: Vector[Int], r: Vector[Int], acc: Vector[Int]): Vector[Int] = { (l.isEmpty, r.isEmpty) match { // If either side is empty, just add // the non-empty side to the accumulator. case (true, _) => acc ++ r case (_, true) => acc ++ l // Compare the head elements, and add // the lesser head value to the // accumulator. Then call recursively. case _ => val lh = l.head val rh = r.head val (next, l2, r2) = if (lh < rh) (lh, l.tail, r) else (rh, l, r.tail) mergeWith(l2, r2, acc :+ next) } } mergeWith(left, right, Vector[Int]()) }

Now `mergeSort`

can use `bisect`

and `merge`

to break down the vector and then merge it back together:

def mergeSort(as: Vector[Int]): Vector[Int] = as match { case Vector() => as case Vector(a) => as case _ => val (l, r) = bisect(as) merge(mergeSort(l), mergeSort(r)) } val xs: = Vector(43,48,3,23,28,6,25,43,16) val sorted: Vector[Int] = mergeSort(xs) // sorted: Vector[Int] = // Vector(3, 6, 16, 23, 25, 28, 43, 43, 48)

**A quick announcement**: I’ve got some instructional material to develop. Unfortunately it’s going to take up a fair amount of my time. This is probably the last Scala Saturday post for a little while, but I hope to pick back up in a month or two.