Merge Sort

Merge Sort


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)
         if a2.empty?
             return ret.concat(a1)

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

Get Wicked Cool Ruby Scripts now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.