Wicked Cool Ruby Scripts

Merge Sort

Merge Sort

mergeSort.rb

This sorting algorithm does exactly what the name describes: It merges two sort elements. The algorithm splits the main data set into smaller subsets of one element. It then takes the first and second elements and sorts them, creating a subset. The result of the initial subset is merged and sorted with the next element. This process is done recursively until all elements have been merged back into the main data set. Interestingly, this algorithm is the first to address performance in significantly large data sets.

The Code

 require 'benchmark'

 def merge(a1, a2)
     ret = []

     while (true)
         if a1.empty?
             return ret.concat(a2)
         end
         if a2.empty?
             return ret.concat(a1)
         end

 if a1[0] < a2[0] ret << a1[0] a1 = a1[1...a1.size] else ...