Get it? Because sorting problems are as old as...? Oh, nevermind.

A Swift Sorting Problem

Well, an edge case really. If you're going to grill me on it...

Through a series of unfortunate events, I recently became aware that Swift’s default sorting algorithms can have an unstable result. This not only frustrated me, it left me rather annoyed that even as of Swift 3 there is no stable-by-default sort included to make our lives easier.

Normally, such a thing wouldn't bother me. In fact for the majority of the time, I couldn't possibly care less about such things. However, on this particular day it bothered me greatly. Time pressure and a ridiculously high cost to having the data out of the correct order forced me to work my way around this problem, and to do so quickly.

Now, I'm going to assume that many reading this article haven't the slightest inkling of an idea as to what "stable" sorting means. Because of this, I'll explain it below in the way that I understand it:

A sort can only be considered stable when two equal objects to be sorted, get left well alone by the algorithm.

Really, a developer should only care about their sorted list being stable iff there is a monumental cost to it not being so. To be honest, I was a touch disappointed in myself. I naïvely assumed that sort() would work perfectly for all of our use cases, and that I didn’t need to pay too much attention to sorting the data.

Assumption is the “Mother of all Fuck-Ups.” — Me

Sorting problems are as old as the hills. They are extremely common, and could even be the cause of bugs in your code that seem impossible to solve completely. If you’ve used Swift for longer than approximately four seconds, chances are you've used sort() in your Swift code a few times. Have you paid enough thought to potential edge cases?

After a few four letter words and a “why do you think this bug is happening” discussion with my team, a cursory glance at the Quick Help panel for sort() yielded us a warning which stated that the unstable algorithm was most-likely the cause of my issue. After a quick examination, we proved together that it was.

Why Did It Suck For Us?

The app that we happened to be working on, relied heavily on accurate data being presented to the customer. Basically, the user could subscribe to a service and it would bill them monthly, these subscriptions could also be stopped.

The issue reared its ugly head whenever we went to query a list of a user’s subscription history. We wanted to sort the data so that the history of a given subscription, and the parent list itself, was ordered from oldest to most recent.

For reasons only known to the backend, a subscription’s status would discernibly change — for example from REQUESTED to ACTIVE to STOPPED — 99.999% of the time. However, an infinitesimal 0.001% of the time, the status would change instantaneously. Therein lies the problem. Because I was sorting by date, the list ended up out of order because certain items in it were considered equal and Swift’s sorting algorithm was unstable.

My Solution

Now, while I might’ve been able to provide more metrics to sort(), I opted to use a more brute-force solution right off the bat. Since Swift is still something quite new to me, I went with a solution from good-old Objective-C.

let sortedArray = (parentList as NSArray).sortedArrayWithOptions(.Stable, usingComparator: ({ (lhs, rhs) -> NSComparisonResult in
let lhs = (lhs as! Record) // Replace with your data type
let rhs = (rhs as! Record) // Same as above
if lhs.date == rhs.date {
return .OrderedSame
}
return lhs.date.compare(rhs.date)
}));

It may not be the best Swift code around, but it helped me get the job done.

Here’s hoping my trials and tribulations save you from the same disaster!

About Us

At jtribe, we proudly craft software solutions for iOS, Android and Web and are passionate about our work. We’ve been working with iOS and Android platforms since day one and are one of the most experienced mobile development teams in Australia. We measure success on the impact we have, and with over six-million end users we know our work is meaningful, and that continues to be our driving force.

Benjamin J. Dietzkis

Written by

iOS Guy @ Mercari Inc. 日本語. EN. 東京住まい

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade