The impetus behind this sort timing test is from the Coursers “algo” course and in particular the Quicksort section. One comment was that sorting was so fast that the cost need not even be considered. It seem that on an iPad (version 3) sort times of short NSString objects in an NSArray are cheap for approximately n < 10,000.
The NSMutablearray contains unique strings of 8 digits in random order. The sort was statement was:
where ma is the afore mentioned NSMutablearray.
Times were calculated in 1,2,5 step increments from 10 to 500,000 items on an iPad (version 3).
The three lines on the graph are:
Blue: the time in ms so sort the array
Green: n log(n) for a visual slope reference
Yellow: n^2 for a visual slope reference
It can be seen (and numerically verified) that the sort time is very slightly greater than n log(n). This is in agreement with sort times to be expected from the Quicksort algorithm.
The table below contain the sort times as well a n log(n and n^2 for comparison:
|items||iPad (3) ms||iPhone 3GS ms||n log(n)||n^2|