Cydia Founder Saurik on iPod Sorting Algorithm Error


Have you ever been unable to find a song or track on your Music application while searching? Here’s why

Scrolling through my iPod collection, sometimes I get frustrated when I cannot find a song that I want to listen to on my iPod. Then I jump over to the iTunes app to redownload it, only to find out that I already have it. Has this ever happened to you?

The screenshots are from a 4th-gen iPod running iOS 6. Looking for a band and figured it was accidentally deleted, then realised everything was muddled up. A-K are fine, and W-Z/numbers are fine. It’s just K-W that are muddled. Albums and Artists have the messed up alphabet, not in Songs.

Here is Jay Freeman’s explanation of why these issues happen via Reddit:

The sorting algorithm that most people expect to be used in this situation is incredibly complex, involving deletion of articles (“the”, “a”), keeping numbers in numeric order (“1000″ comes after “2″), and locale-sensitive awareness of how to order accented characters.

Meanwhile, unlike with contacts (which people might have, at the extreme, in the low thousands, and which tend to have only few special cases), people tend can and occasionally do get the 64GB iPod and fill it up with tens of thousands of tracks and almost all of them are of some weird special form that needs to be sorted insanely.

The problem is one that is really hard: I have gone to great lengths in crazy-algorithm design to make this kind of thing scale well in Cydia (which often deals locally with tens of thousands of packages), but if you have certain “worst case” package sets (which I have humorously, on occasion, “policed for” in the default repositories ;P), it can get “really slow” (a second or so to setup a list) or “slightly weird” (I have to cut some corners).

Apple’s solution, as far as I understand / remember, is designed to be nearly optimal under the expectation that the only way to add tracks is to do a complex syncing process with iTunes: it pre-computes keys used to do the ordering, and uses these precomputed keys to accelerate the sorting required when you bring up a list.

Whether these are radix keys (similar to how I handle this in Cydia, albeit locally) or simply “the numeric ranked order for each track”, I don’t know. However it is, though, it is stored with the actual “this is the name” information, but is a separate data item that technically can be “wrong”.

One thereby presumes that this metadata got “out of sync” somehow. Now, how this happened? I have no clue. However, as a bunch of people decided to start talking about why this happened (with bryanlharris providing a reasonable explanation), I figured I’d toss in this look at the “reason they would do this in the first place”.

For more updates you can follow iOSVlog on Twitter, Like on Facebook, or Add us to your circles on Google+