Re: qsort_b in Swift


Quincey Morris
 

On Sep 16, 2017, at 20:40 , Gerriet M. Denkmann <g@...> wrote:

It would be interesting to know what kind of optimisation magic Swift does here.

My guess is that this is not a compiler-related difference, but rather the effect of different algorithms. The performance depends on the initial ordering of the array. My recollection of this subject is hazy, but I think qsort is helped by an array that is already partially ordered, which yours is not. (This is not necessarily an artificial condition. For example, if you add 100 elements to the end of an array of 1000 elements that was already sorted, you will end up with a very non-random array to be re-sorted.)

Qsort is also limited to one algorithm. It’s not impossible that the Swift array sort function does a quick analysis of the array and chooses an algorithm that looks like it will work better than others.

So, yes, it’s very nice to know that Swift’s default sort is something that can be trusted.

Join {cocoa@apple-dev.groups.io to automatically receive all group messages.