Class: Sorting::LibrarySort

Inherits:
Object
  • Object
show all
Extended by:
Helper
Defined in:
lib/sorting/library_sort.rb

Constant Summary collapse

TEST_DATA_SIZE = 
100_000
GAP = 
8

Class Method Summary collapse

Methods included from Helper

sort

Class Method Details

.sort(data) ⇒ Object

Library sort Comparison sort Insertion Stable Time complexity: Ω(n), Ө(nlogn), O(n2) Space complexity: O(n) Very fast, Adaptive, Online Requires extra space



18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
# File 'lib/sorting/library_sort.rb', line 18

def self.sort(data)
  sorting_data = Array.new data.size
  steps = build_steps data
  step_counts = {}
  data.each do |e|
    step = binary_search_first_bigger_value steps, e
    step_counts[step] = (step_counts[step] || 0) + 1
  end
  step_locations = {}
  last_location = 0
  last_step_item_count = 0 
  steps.each do |step|
    last_location += last_step_item_count
    step_locations[step] = last_location
    last_step_item_count = step_counts[step]
  end
  data.each do |e|
    step = binary_search_first_bigger_value steps, e
    sorting_data[step_locations[step]] = e
    step_locations[step] += 1
  end
  InsertionSort.sort! sorting_data
  sorting_data
end