# Sorting a small given/fixed number of values

**URL:** <https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222>\
**Category:** Using Swift\
**Tags:** sorting, challenge\
**Created:** [January 29, 2020, 6:40pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222 "2020-01-29T18:40:39Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![Jens](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jens/32/12903_2.png) [@Jens](https://forums.swift.org/u/Jens)\
**Post date:** [January 29, 2020, 6:40pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/1 "2020-01-29T18:40:40Z")

</div>

Let's say we want to make sure that a small number of separate values/variables/constants (ie _not_ an `Array`) are ordered (because eg the remaining code becomes easier to write if `a` `b` and `c` are known to be in ascending order).

For **two elements** it's just:

```swift
let (a, b) = p > q ? (q, p) : (p, q)

```

or ( for mutable p q ):

```swift
if p > q { swap(&p, &q) }

```

For **three elements** it's not as straight forward, but if we know that our code won't be executed super frequently and just want to get it done, we might write something like:

```swift
let tmpAr = [p, q, r].sorted()
let (a, b, c) = (tmpAr[0], tmpAr[1], tmpAr[2])

```

or ( for mutable p q r ):

```swift
if p > q { swap(&p, &q) }
if q > r { swap(&q, &r) }
if p > q { swap(&p, &q) }

```

It's a lot of code for something as simple as that, it might be hard to spot a mistake in it and if efficiency matters we would need to spend some more time on improving it.

More than a couple of times, I've found myself needing this kind of sorting (for 3 or 4 elements).

> **Here's an example, for 2 and 3 values.**
>
> ```swift
> extension Disk {
> /// Returns the smallest disk enclosing two other disks `a` and `b`.
> init(smallestDiskEnclosing a: Disk, and b: Disk) {
> // Start by sorting the disks by ascending radius, smallest first:
> let (a, b) = a.radius < b.radius ? (a, b) : (b, a)
> let cDist = simd_distance(a.center, b.center)
> // If one of the disks (b) encloses the other (a), we are done:
> guard cDist + a.radius > b.radius else { self = b; return }
> let enclosingDiskR = (cDist + a.radius + b.radius) * 0.5
> let t = (enclosingDiskR - a.radius) / cDist
> self = Disk(center: simd_mix(a.center, b.center, .init(t, t)),
> radius: enclosingDiskR)
> }
> 
> /// Returns the smallest disk enclosing three other disks `a`, `b`, and `c`.
> init(smallestDiskEnclosing a: Disk, b: Disk, and c: Disk) {
> // Start by sorting the disks by ascending radius, smallest first:
> let (a, b, c) = ...
> // ...
> }
> 
> /// Returns the smallest disk enclosing a sequence of disks.
> init(smallestDiskEnclosing: S) where S: Sequence, S.Element == Disk {
> // Problem is solved recursively (terminal case is 3 disks or less) ...
> // ...
> }
> }
> 
> ```

It would be nice to solve this once and for all, and why not in the form of a group challenge here?

* * *

## Challange:

**Come up with something that makes this kind of sorting, for 2, 3 and 4 elements (of the same type), nice and efficient!**

Ideally, it should probably support both immutable and mutable (`inout`) usage, perhaps even unsafe usage on raw memory (for sorting eg successive chunks of four `Float` values in a big memory block).

* * *

I haven't thought much about design, but perhaps something like this on the call site:

```swift
let (a, b, c) = sorted(p, q, r) // ascending order

```

```swift
let (a, b, c) = sorted(p, q, r, by: >) // descending order

```

```swift
sort(&p, &q, &r)

```

```swift
sort(&p, &q, &r, by: >)

```

and maybe even something like:

```swift
sort4(elementsOfType: Float.self, startingAt: ptr)

```

---

<div class="post-metadata">

**Author:** ![Martin](https://avatars.discourse-cdn.com/v4/letter/m/73ab20/32.png) [@Martin](https://forums.swift.org/u/Martin)\
**Post date:** [January 29, 2020, 6:56pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/2 "2020-01-29T18:56:48Z")

</div>

I am not an expert on this topic, but [Sorting networks](https://en.wikipedia.org/wiki/Sorting_network) might be what you are looking for.

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [January 29, 2020, 9:12pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/3 "2020-01-29T21:12:52Z")

</div>

> [@Martin](#):
>
> I am not an expert on this topic, but [Sorting networks](https://en.wikipedia.org/wiki/Sorting_network) might be what you are looking for.

Yes, this is exactly right.

Here’s a sample implementation for 2, 3, and 4 elements:

> **In-place**
>
> ```swift
> func sort<T>(_ a: inout T, _ b: inout T, by areInIncreasingOrder: (T,T)->Bool) {
> if areInIncreasingOrder(b, a) { swap(&a, &b) }
> }
> 
> func sort<T>(_ a: inout T, _ b: inout T, _ c: inout T, by areInIncreasingOrder: (T,T)->Bool) {
> sort(&a, &b, by: areInIncreasingOrder)
> sort(&a, &c, by: areInIncreasingOrder)
> sort(&b, &c, by: areInIncreasingOrder)
> }
> 
> func sort<T>(_ a: inout T, _ b: inout T, _ c: inout T, _ d: inout T, by areInIncreasingOrder: (T,T)->Bool) {
> sort(&a, &b, by: areInIncreasingOrder)
> sort(&c, &d, by: areInIncreasingOrder)
> sort(&a, &c, by: areInIncreasingOrder)
> sort(&b, &d, by: areInIncreasingOrder)
> sort(&b, &c, by: areInIncreasingOrder)
> }
> 
> ```

> **In-place \`Comparable\`**
>
> ```swift
> func sort<T: Comparable>(_ a: inout T, _ b: inout T) {
> sort(&a, &b, by: <)
> }
> 
> func sort<T: Comparable>(_ a: inout T, _ b: inout T, _ c: inout T) {
> sort(&a, &b, &c, by: <)
> }
> 
> func sort<T: Comparable>(_ a: inout T, _ b: inout T, _ c: inout T, _ d: inout T) {
> sort(&a, &b, &c, &d, by: <)
> }
> 
> ```

> **Out-of-place**
>
> ```swift
> func sort<T>(_ a: T, _ b: T, by areInIncreasingOrder: (T,T)->Bool) -> (T, T) {
> var (x, y) = (a, b)
> sort(&x, &y, by: areInIncreasingOrder)
> return (x, y)
> }
> 
> func sort<T>(_ a: T, _ b: T, _ c: T, by areInIncreasingOrder: (T,T)->Bool) -> (T, T, T) {
> var (x, y, z) = (a, b, c)
> sort(&x, &y, &z, by: areInIncreasingOrder)
> return (x, y, z)
> }
> 
> func sort<T>(_ a: T, _ b: T, _ c: T, _ d: T, by areInIncreasingOrder: (T,T)->Bool) -> (T, T, T, T) {
> var (w, x, y, z) = (a, b, c, d)
> sort(&w, &x, &y, &z, by: areInIncreasingOrder)
> return (w, x, y, z)
> }
> 
> ```

> **Out-of-place \`Comparable\`**
>
> ```swift
> func sort<T: Comparable>(_ a: T, _ b: T) -> (T, T) {
> sort(a, b, by: <)
> }
> 
> func sort<T: Comparable>(_ a: T, _ b: T, _ c: T) -> (T, T, T) {
> sort(a, b, c, by: <)
> }
> 
> func sort<T: Comparable>(_ a: T, _ b: T, _ c: T, _ d: T) -> (T, T, T, T) {
> sort(a, b, c, d, by: <)
> }
> 
> ```

---

<div class="post-metadata">

**Author:** ![Jens](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jens/32/12903_2.png) [@Jens](https://forums.swift.org/u/Jens)\
**Post date:** [January 29, 2020, 9:20pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/4 "2020-01-29T21:20:10Z")

</div>

Very nice!

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [January 29, 2020, 9:34pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/5 "2020-01-29T21:34:12Z")

</div>

For 3 elements specifically, you could also write something like this with a giant `switch`:

> **Alternative sort3 implementation**
>
> ```swift
> func sort3<T>(_ a: inout T, _ b: inout T, _ c: inout T, by areInIncreasingOrder: (T,T)->Bool) {
> let ab = areInIncreasingOrder(a, b)
> let ac = areInIncreasingOrder(a, c)
> let bc = areInIncreasingOrder(b, c)
> switch(ab, ac, bc) {
> case (false, false, false) /*c<b<a*/ : swap(&a, &c)
> case (false, false, true) /*b<c<a*/ : swap(&a, &c); swap(&a, &b);
> case (false, true, false) /*CYCLE*/ : fatalError()
> case (false, true, true) /*b<a<c*/ : swap(&a, &b)
> case (true, false, false) /*c<a<b*/ : swap(&a, &b); swap(&a, &c)
> case (true, false, true) /*CYCLE*/ : fatalError()
> case (true, true, false) /*a<c<b*/ : swap(&b, &c)
> case (true, true, true) /*a<b<c*/ : break
> }
> }
> 
> ```

That’s a lot harder to reason about (at least for me), and you’d probably need to check [swift.godbolt.org](http://swift.godbolt.org) to see how each version optimizes.

---

<div class="post-metadata">

**Author:** ![Jens](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jens/32/12903_2.png) [@Jens](https://forums.swift.org/u/Jens)\
**Post date:** [January 29, 2020, 10:16pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/6 "2020-01-29T22:16:52Z")

</div>

I might be missing something, but your latest version starts by doing three comparisons, and then I guess the switch has to do some more.

The best/lucky case for three elements should only require _two_ comparisons, no?

```swift
if a <= b {
    if b <= c {
        // Ah, done!
    } else {
        // ...
    }
} else {
    // ...
}

```

---

<div class="post-metadata">

**Author:** ![Nevin](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/nevin/32/617_2.png) [@Nevin](https://forums.swift.org/u/Nevin)\
**Post date:** [January 29, 2020, 10:21pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/7 "2020-01-29T22:21:33Z")

</div>

> [@Jens](#):
>
> I might be missing something, but your latest version starts by doing three comparisons, and then I guess the switch has to do some more.

It makes 3 calls to `areInIncreasingOrder`, which might involve arbitrarily large amounts of work. Then it performs a `switch` over a 3-tuple of `Bool`s, which could in theory be optimized quite well.

I’m not convinced that nesting the conditionals would actually be a win, given the nature of modern processor execution. I suspect branchless compare-and-swap will be most efficient, though again you’d need to look at the optimized compiled output for each version to see what looks best.

---

<div class="post-metadata">

**Author:** ![Jens](https://sea2.discourse-cdn.com/swift/user_avatar/forums.swift.org/jens/32/12903_2.png) [@Jens](https://forums.swift.org/u/Jens)\
**Post date:** [January 29, 2020, 10:40pm UTC](https://forums.swift.org/t/sorting-a-small-given-fixed-number-of-values/33222/8 "2020-01-29T22:40:48Z")

</div>

> [@Nevin](#):
>
> though again you’d need to look at the optimized compiled output for each version to see what looks best.

And while doing so, remember to [watch out](https://forums.swift.org/t/swifts-unpredictable-efficiency/13506) / search for, isolate and report any missed optimizations caused by the exact formulation (including seemingly irrelevant context) of your benchmarking code.  
: )