SkTInsertionSort tweak.
'Unoptomized' insertion sort swaps the 'insert' value multiple times
inside the main loop before it finds its place. However, this has the
advantage that if the 'insert' element is already not less than any
element in the sorted partition no moves are made at all.
The 'optimized' insertion sort present before this CL moves the 'insert'
value into a temporary (creating a 'hole') and then moves already sorted
elements until the 'insert' element finds its place. This has the
disadvantage of always moving the 'insert' element out of the list and
then re-inserting it, even if this was unnecessary.
This CL further optimizes the insertion sort by moving the first test of
the main loop to before moving the 'insert' element into the temporary.
This is expected to increase the code size by a few instructions but
avoids the useless non-moves. There will actually be one fewer
comparison per element comsidered (the initial 'left < hole' predicate
is always true when entering the inner loop).
GOLD_TRYBOT_URL= https://gold.skia.org/search?issue=4022
Change-Id: I33158b7781e4dbec1f1b76c0bf43ebe169075733
Reviewed-on: https://skia-review.googlesource.com/4022
Reviewed-by: Mike Klein <mtklein@chromium.org>
Commit-Queue: Ben Wagner <bungeman@google.com>
1 file changed