Class: Sorting::MergeSort

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

Constant Summary collapse

TEST_DATA_SIZE = 
100_000
SIZE_FOR_INSERTION = 
15

Class Method Summary collapse

Methods included from Helper

sort

Class Method Details

.sort(data) ⇒ Object

Merge sort Comparison sort Merging Stable Time complexity: O(nlogn), Ө(nlogn), O(nlogn) Space complexity: O(n) Support parallelization Better for linked list Efficient at handling slow-to-access sequential media



18
19
20
21
22
23
24
25
26
27
 
# File 'lib/sorting/merge_sort.rb', line 18

def self.sort(data)
  if data.size < SIZE_FOR_INSERTION
    data = Sorting::InsertionSort.sort(data) 
    return data
  end
  mid   = data.size / 2
  left  = data[0...mid]
  right = data[mid...data.size]
  merge(sort(left), sort(right))
end