core :: Comparator :: insertion_sort
array
between from
and to
indicesWorst case: O(n^2), average case: O(n^2)
var a = [5, 2, 3, 1, 4]
default_comparator.insertion_sort(a, 0, a.length - 1)
assert a == [1, 2, 3, 4, 5]
# Insertion-sort `array` between `from` and `to` indices
# Worst case: O(n^2), average case: O(n^2)
#
# var a = [5, 2, 3, 1, 4]
# default_comparator.insertion_sort(a, 0, a.length - 1)
# assert a == [1, 2, 3, 4, 5]
fun insertion_sort(array: Array[COMPARED], from: Int, to: Int) do
for i in [from..to] do
var j = i
while j > 0 and compare(array[j], array[j - 1]) < 0 do
array.swap_at(j, j - 1)
j -= 1
end
end
end
lib/core/collection/sorter.nit:163,2--177,4