O'Reilly logo

Wicked Cool Ruby Scripts by Steve Pugh

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required