Perhaps this is mysteries that are beyond my ken, but reading through this thread I am quite puzzled by the number fifteen. That is quite a remarkable difference, especially when the sort-algorithm does not change. In the end, what is it about this algorithm that produces essentially a 2**4-fold improvement? And, does this improvement hold in a linear fashion as the number of records grows (but stays within the confines of the available process working-set)?
It is, of course, quite clear how it works: the list is sorted irrespective of name, then partitioned into manager vs. non-manager, then one sorted sublist is put in front of the other. But fifteen is still a very counter-intuitive spread between the two ... I feel reluctant to shout “eureka!” based on just this.