# Writing A Generic Stable Sort

One more post on writing generic algorithms. Let’s take a non-trivial non-generic algorithm and write a generic version. We’ll port a Java implementation of merge sort, and also look at some other interesting things we might do to some Java code when converting it to Swift.

Why bother with a merge sort? Well, the standard library comes with a very efficient in-place sort, based on the introsort, but it’s not a stable sort – that is, two otherwise equal entries aren’t guaranteed to stay in the same order, something that is often expected in things like grids that sort when you click a column header.

To start off, here is a Java version of a bottom-up merge sort, taken from Sedgewick, in all its Java-y C-for-loop-y zero-based-integer-index-y glory. Check out the vertigo-inducing braceless `for` loops!

```public class Merge {
private static Comparable[] aux;

private static void merge(Comparable[] a, int lo, int mid, int hi) {
int i = lo, j = mid+1;

for (int k = lo; k <= hi; k++)
aux[k] = a[k];

for (int k = lo; k <= hi; k++)
if      (i > mid)
a[k] = aux[j++];
else if (j > hi)
a[k] = aux[i++];
else if (aux[j].compareTo(aux[i]) < 0)
a[k] = aux[j++];
else
a[k] = aux[i++];
}

public static void sort(Comparable[] a) {
int N = a.length;
aux = new Comparable[N];
for (int sz = 1; sz < N; sz = sz+sz)
for (int lo = 0; lo < N-sz; lo += sz+sz)
merge(a, lo, lo+sz-1, Math.min(lo+sz+sz-1, N-1));

}
}
```

This is generic on the array’s contents, but not on the container (not that you couldn’t write a container-generic version in Java too, but this isn’t a Java blog, I get quite enough Java in my day job thanks).

A good first step to turn this into a generic Swift algorithm would be just to port it to `Array` first. But even this presents some interesting problems – it’s not just a straight port, despite Java and Swift’s common ancestry. So let’s port it to Swift and make it more Swift-like at the same time, while keeping the algorithm broadly similar (speaking of which, yes, I know you can do it recursively but we’ll stick with the iterative version).

A first step would be ditching the very Java-esque practice of creating a class just to wrap some static methods. This passes for normal in the kingdom of nouns, but in Swift this would be more suited to an extension, with `self` taking the place of the `a` parameter:

```extension Array {
// really this ought to be marked rethrows but
// let’s ignore that to keep things simple...
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count
// etc.
}
}
```

Why not write a version for `Array where Element: Comparable`? Well, `Comparable` conforms to `Equatable`, which has the following stern warning in its comment:

Equality implies substitutability. When x == y, x and y are interchangeable in any code that only depends on their values.

When needing a stable sort, the whole point is that you’re only comparing part of the values – you sort by last name, while wanting rows with the same last name to stay in the same order. Obviously that means that the two values you’re comparing are not substitutable. So it probably only makes sense to implement this sort with a comparator function. Never, ever, conform to `Comparable` by comparing only part of the visible properties of your type.

The first problem we face is that temporary storage array `aux`. Well, two problems really. The Java version does something that would be pretty monstrous in anything other than a textbook example – it uses a static variable. This would be fine for single-threaded code but if ever you used this same function simultaneously from two threads (even on two different arrays) then kerplowie. Brings back fond memories of debugging production problems from someone calling `strtok` from multiple threads. Sorry, did I say fond? I meant traumatic.

Anyway, even if you wanted to do it with a static property, you couldn’t, because you can’t add static variables to generic types in Swift. (if you wonder why – think about what would happen if there were a static property on `Array` – should there be just one static variable for both `[Int]` and `[String]`, or two different ones?)

So we need another way. We could just declare a new array inside `merge` every time, but that would allocate fresh array storage on every call, which would be horribly inefficient.

Alternatively, you could create the array once in the `sort` function, just like in the Java version, but then pass it as an argument into the `merge` function. This would ugly up the code a bit. But more importantly, it wouldn’t work with Swift arrays, because they are value types. If you created an array in `sort` then passed it into `merge`, it could be copied(-on-write), not re-used, which would be even worse than declaring a new one.

(If you are thinking `inout` or `var` is the solution, you’re also out of luck there. Despite what that call-site ampersand might imply, `inout` in Swift is not pass-by-reference, but rather pass-by-value-then-copy-back. `var` is similarly no help – it’s just shorthand for declaring a second mutable variable and assigning it the value of the parameter. Plus `var` is going away soon, probably partly because it caused this kind of confusion. UPDATE: per @jckarter, the `inout` situation may not be so clear-cut and ought to work in this case)

You could use reference-type storage, like `NSArray`, instead. Or you could allocate some memory yourself using `UnsafeMutablePointer`. Or use a `Box` class to wrap an array in a reference type. But here’s a perhaps neater alternative – declare `merge` as an inner function, and make it a closure that captures a local array variable:

```extension Array {
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count
// declare a local aux variable
var aux: [Element] = []
// make sure it has enough space
aux.reserveCapacity(self.count)

// local merge function that can operate on (capture) self
func merge(lo: Int, _ mid: Int, _ hi: Int) {
// merge captures the aux variable _by ref_
// we can now use aux to merge self
}

for etc. {
merge(etc.)
}

}
}
```

When a function closes over a variable, it captures it by reference. This means that `merge` and the outer sorting function will share the same instance, exactly what we want. Unlike the static approach, there’s no risk that a second call will use the same storage – `aux` is still local to the call to sort, and two different calls will use two different local storage arrays, and so will their inner variables. The one downside of this is we wouldn’t be able to expose our `merge` function publicly, even though it could be a useful algorithm in its own right.

By the way, even though we declared `merge` with `func`, it is still a closure – don’t conflate the term closure (functions plus captured environment), with closure expressions (the Swift term for the shorthand syntax for writing anonymous functions). Local functions declared with `func` are just as closurey as closure expressions.

OK that solves that problem, but there’s a second issue. In the Java version, the array is declared to be a given fixed size:

```    aux = new Comparable[N];
```

and then the `merge` function just plunges in and uses bits of it:

```    for (int k = lo; k <= hi; k++)
aux[k] = a[k];
```

Here’s another place where both Java and Swift start from their common ancestor, but then Java zigs while Swift zags. In C, you declare a variable, and then you can immediately read from it without giving it a value. Everyone agrees that this is all very horrible and monstrous, but to not have that you have to choose a path – give everything a default value, like in Java, or ban reading until you’ve written, like in Swift.

There are maybe performance reasons why Swift’s choice is better. But really, it was forced by other factors. In Java, everything is either a primitive type, or a reference. With such a limited set of types it’s reasonable to give everything a default value – either zero, empty, or null. But Swift isn’t so simple. It doesn’t even really have “primitive” types – even `Int` is a struct. And while it has references, they aren’t always nullable. So everything having a default isn’t really an option.

So it follows that in Swift you can’t have an `Array` where you just declare it to be a given size then plunge in getting and setting elements at arbitrary indices. I mean, you could write an array that worked like that, but then you’d have to track internally when values for given index had been set or not. So instead, to make an array have `n` elements, you have to put `n` in. You can do that easily with `Array(count: n, repeatedValue: ???)`, but for our purposes, what would you put as the value? `Element` is completely generic, you don’t know anything about it, so there’s no reasonable default.

One solution is to use an array of `Optional`. That way, you can set them all to `nil`. Probably this would be one of those rare legit uses of an implicitly-unwrapped optional – where you can prove that at the time you use the optional that it wil never be `nil`, so there’s no harm unwrapping it implicitly. In fact, you’d like it to assert if you ever unwrapped a `nil`, as this would mean there was something horribly wrong with your logic.

```extension Array {
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count
var aux = Array<Element!>(count: N, repeatedValue: nil)

func merge(lo: Int, _ mid: Int, _ hi: Int) {
var i = lo, j = mid+1

for var k = lo; k <= hi; k++ {
aux[k] = self[k]
}

for var k = lo; k <= hi; k++ {
if      i > mid { self[k] = aux[j++] }
else if j > hi  { self[k] = aux[i++] }
else if isOrderedBefore(aux[j],aux[i])
{ self[k] = aux[j++] }
else            { self[k] = aux[i++] }
}
}

for var sz = 1; sz < N; sz = sz+sz {
for var lo = 0; lo < N-sz; lo += sz+sz {
merge(lo, lo+sz-1, min(lo+sz+sz-1, N-1))
}
}

}
}
```

This now works, and is pretty much like the Java version. But implicitly-unwrapped optionals are a bit unpleasant, and anyone unhappy about the merge sort’s linear space requirements might blanche at the extra bits they take up. And the rest isn’t very Swift-y. Those `for` loops and `++` are not long for this world, and it’ll bit a bit painful to translate this into a fully generic function.

• Flip it around and have the merge logic copy into the `aux` array, then copy back into `self`, using `append`, removing the need to size it up at the beginning.
• At the same time, we can switch the `for` for a `while`, and ditch the `++`
• Switch from closed ranges (up-to-and-including `hi`) to half-open ranges (up-to but not including `hi`) since this is more the Swift convention (and will be easier in the next part)
• Use `appendContentsOf` and `replaceRange` instead of hand-rolled loop-and-assign

which gives us this merge function:

```  // ditch the optionals
var aux: [Element] = []
// make sure aux has enough memory to store a fully copy
// (note, does _not_ actually increase aux.count)
aux.reserveCapacity(N)

func merge(lo: Int, _ mid: Int, _ hi: Int) {
// wipe aux, but keep the memory buffer
// at full size each time around
aux.removeAll(keepCapacity: true)

var i = lo, j = mid
while i < mid && j < hi {
// append the lesser of either element
if isOrderedBefore(self[j],self[i]) {
aux.append(self[j])
j += 1
}
else {
aux.append(self[i])
i += 1
}
}
// then append the stragglers
// (one of the next 2 lines will be a no-op)
aux.appendContentsOf(self[i..<mid])
aux.appendContentsOf(self[j..<hi])
// then copy the sorted temp storage back into self
self.replaceRange(lo..<hi, with: aux)
}
```

Finally, we need to do the same for the sorting `for` loops:

```  for var sz = 1; sz < N; sz = sz+sz {
for var lo = 0; lo < N-sz; lo += sz+sz {
merge(lo, lo+sz-1, min(lo+sz+sz-1, N-1))
}
}
```

That outer `for` is kinda sneaky, since it’s doubling `sz` each time around the loop, so that needs a `while` rather than a `stride`. The inner one is a lot simpler though, it’s just striding over the array by a constant `sz*2` each time. Moving to half-open rather than closed ranges makes this a whole lot easier, since it gets rid of all the annoying `-1`s littered about:

```  var sz = 1
while sz < N {
for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
sz *= 2
}
```

This leaves us with a final version, Swiftified if not yet generic. It’s a little more verbose than the original Java, but mainly because of the loss of the compact `for` and `++` notation, and hopefully a bit more readable for it:

```extension Array {
public mutating func stableSortInPlace(
isOrderedBefore: (Element,Element)->Bool
) {
let N = self.count

var aux: [Element] = []
aux.reserveCapacity(N)

func merge(lo: Int, _ mid: Int, _ hi: Int) {

aux.removeAll(keepCapacity: true)

var i = lo, j = mid
while i < mid && j < hi {
if isOrderedBefore(self[j],self[i]) {
aux.append(self[j])
j += 1
}
else {
aux.append(self[i])
i += 1
}
}
aux.appendContentsOf(self[i..<mid])
aux.appendContentsOf(self[j..<hi])
self.replaceRange(lo..<hi, with: aux)
}

var sz = 1
while sz < N {
for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
sz *= 2
}
}
}
```

## Making it work on any random-access collection

OK, now to make it generic. A lot of that rework from before will make this easier.

First, to make this an extension of a protocol instead of protocol instead of `Array`. We actually used `self.replaceRange`, so let’s make it an extension of `RangeReplaceableCollectionType` (maybe a bit of an overconstraint – you could do without it and just make do with `MutableCollectionType`, but let’s ignore that). Plus the `where` clauses. We know the index needs to be random-access. We also rely on slicing, so per the previous article on this topic, we need to require `SubSequence` contains the same elements as the sequence:

```extension RangeReplaceableCollectionType
where
Index: RandomAccessIndexType,
SubSequence.Generator.Element == Generator.Element {
```

Doing this in Xcode will now show you all the places where you are relying on assumptions that no longer hold now you aren’t just writing against `Array` (though, more spring up as you fix these…) Easy ones first. `Generator.Element` instead of just `Element`:

```    public mutating func stableSortInPlace(
isOrderedBefore: (Generator.Element,Generator.Element)->Bool
) {
let N = self.count

var aux: [Generator.Element] = []
```

Next, `aux.reserveCapacity`. We want to reserve the number of elements, but that comes (via `aux.count`) in the form of a `Self.Distance`. Remember, distances are always integers, but they might not be `Int`. We have to use `numericCast` to fix this:

```            aux.reserveCapacity(numericCast(N))
```

I admit, I haven’t quite got my head around whether this is an OK thing to do or not. For almost every reasonable circumstance, this will be a no-op, since `Distance` will be an `Int`. If for some reason you were using a class that used a smaller `Distance`, it will upconvert it. There’s a slim chance that `Distance` could be bigger than an `Int` – say if you’re on 32-bit platform but using a collection that used an explicit 64-bit index? Or maybe some giant virtual collection that used a `BigInt`? But for now I shall ignore these possibilities with reckless abandon.

So long as the `where` constraints above, the `merge` function is easy. You just make `lo`, `mid`, and `hi` an `Index` instead of an `Int`:

```    func merge(lo: Index, _ mid: Index, _ hi: Index) {
// the rest is the same
}
```

OK now for the interesting bit, the sorting loops:

```        var sz = 1
while sz < N {
for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
sz *= 2
}
```

The trick is, knowing which ones are indices, and which ones are distances (by which indices will be advanced).

`sz` is a distance. It’s the length by which each pass strides through the collection performing the merge, and which doubles each time around (giving the algorithm its linearithmic performance characteristic). To make that explicit, we need to annotate it with a type (otherwise it’s going to default to being an `Int`):

```    var sz: Index.Distance = 1
```

We already established `N` is the size of the collection and is also a distance, so this is fine (you can compare two distances, and you can double distances):

```  while sz < N {
// inner for stride
sz *= 2
}
```

Finally, the inner stride:

```  for lo in 0.stride(to: N-sz, by: sz*2) {
merge(lo, lo+sz, min(lo+sz*2, N))
}
```

`lo` is an `Index` – that’s what we pass in to `merge` as `lo`. The calculated `mid` and `hi` are indices too. When you see `0` as an index, that really means `startIndex` so we can substitute that.

The only other tricky part is `N`. With zero-based integer indices, `N` could mean two things: the length of the collection, or the end of the collection (i.e. `startIndex.advancedBy(N)`). Here, in this inner loop, it means the latter. So `N-sz` means “back from the end by `sz`“.

Similarly `min(lo+sz*2, N)` means “add `sz*2` to `lo`, or `endIndex` if that goes past the end”. So you could write `min(lo+sz*2, N)`. But there’s already a function for “go this far, but not past this point”. `advancedBy` is overloaded with a version that takes a `limit:` argument. So instead, you can write this as `lo.advancedBy(sz*2,limit: endIndex))`. This is arguably more correct as well, since it could be an error to add a distance to an index to take it past the end of the collection (like with `String` indices).

So we rewrite the inner loop as:

```  for lo in startIndex.stride(to: endIndex-sz, by: sz*2) {
}
```

Again, if you’re doing this in Xcode, the compiler will help you along (for example, it will complain if you’re trying to take the minimum of an index and a distance, since you can’t do that, which is a hint you need an index instead of a distance).

One final gotcha. After you make all these changes and you’re sure everything is correct, the `stride` still won’t compile. We need one more constraint on the protocol: `Index.Distance == Index.Stride`. Yes, this should always be the case (that’s the whole point of making random-access indices strideable – so you can stride by `Distance`), but you still need to make it explicit.

After all this we finally have a fully generic random-access in-place merge sort:

```extension RangeReplaceableCollectionType
where
Index: RandomAccessIndexType,
SubSequence.Generator.Element == Generator.Element,
Index.Distance == Index.Stride {
public mutating func stableSortInPlace(
isOrderedBefore: (Generator.Element,Generator.Element)->Bool
) {
let N = self.count

var aux: [Generator.Element] = []
aux.reserveCapacity(numericCast(N))

func merge(lo: Index, _ mid: Index, _ hi: Index) {

aux.removeAll(keepCapacity: true)

var i = lo, j = mid
while i < mid && j < hi {
if isOrderedBefore(self[j],self[i]) {
aux.append(self[j])
j += 1
}
else {
aux.append(self[i])
i += 1
}
}
aux.appendContentsOf(self[i..<mid])
aux.appendContentsOf(self[j..<hi])
self.replaceRange(lo..<hi, with: aux)
}

var sz: Index.Distance = 1
while sz < N {
for lo in startIndex.stride(to: endIndex-sz, by: sz*2) {
}
sz *= 2
}
}
}
```

I’d suggest you try it out on a mutable random-access collection that doesn’t have integer indices. Except, uh, there aren’t any. There are random-access collections without integer indices – reverse collections for example. Or (with a bit of extension-bullying) `String.UTF16View`. But unfortunately these aren’t mutable! So perhaps I’ve just totally wasted your time. But it was fun, right?

OK so there’s also a much more important benefit to this – it no longer relies on the index starting from zero. Yes, we could have done this for `CollectionType where Index: IntegerType`, but that would probably have been harder, since the compiler would not have helped as much when we made invalid assumptions. The `0` instead of `startIndex` might be easy to catch, but assumptions about when `N` means `endIndx` vs when `N` means `self.count` are much tricker.

Now that we’ve made this change, you can now apply the algorithm in-place to subranges, such as:

```var a = Array(1...5)
a[1..<4].stableSortInPlace(>)
// a = [1,4,3,2,5]
```

And finally, just to check it really is still a stable sort after all this futzing around (that property is easy to break if you make innocent-seeming changes to the order of your `i` and `j` comparisons – something I learned the hard way, forgot, then remembered the hard way during the course of writing this…)

```var pairs = [
(2,1), (2,2),
(3,1), (3,2),
(1,1), (1,2),
(1,3),(2,3),(3,3)
]

pairs.stableSortInPlace { \$0.0 < \$1.0 }
print(pairs.map { \$0.1 })
// if sort is stable, ought to print
// [1, 2, 3, 1, 2, 3, 1, 2, 3]
```