The fastest sort depending on the min and max of the data set would probably be counting sort which is O(n) (in most cases).
Another alternitive would be radix sort which is another non comparitive sort. The key for integer sorting is to look for non comparitive sorting which is O(n).
Any sort that is comparitive will likely need multiple passes to sort data causing them to be like O(log n) and shit which as the data set grows the time it takes to compute the sorted array becomes longer.
Code
~ $ ruby sort.rb
Random array:
[2, 4, 5, 1, 8, 6, 3, 6]
Sorted array:
[1, 2, 3, 4, 5, 6, 6, 8]
Modify one instance of array:
[1, 2, 7, 4, 5, 6, 6, 8]
Sort this array:
[1, 2, 4, 5, 6, 6, 7, 8]
~ $ cat sort.rb
def counting_sort(array)
min = array.min
max = array.max
counts = Array.new(max-min+1, 0);
array.each { |n| counts[n-min] += 1 }
(0...counts.size).map { |i| [i + min] * counts[i] }.flatten
end
puts "Random array: "
p arr = [2,4,5,1,8,6,3,6]
puts "Sorted array: "
p arr2 = counting_sort(arr)
puts "Modify one instance of array: "
arr2[2] = 7
p arr2
puts "Sort this array: "
counting_sort(arr2)
This post was edited by AbDuCt on Aug 3 2018 08:20pm