Skip to content

Instantly share code, notes, and snippets.

@kimhunter

kimhunter/merge_sort.rb

Created October 13, 2011 15:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save kimhunter/1284454 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save kimhunter/1284454 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. Kim Hunter created this gist Oct 13, 2011.
    22 changes: 22 additions & 0 deletions merge_sort.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,22 @@
    #!/usr/bin/env ruby
    # 2011-10-10 20:57:53 +1000

    def merge_sort a
    return a if a.size <= 1
    l,r = split_array a
    result = combine merge_sort(l), merge_sort(r)
    end

    def split_array a
    mid = (a.size/2).round
    return a.take(mid), a[mid, a.size-mid]
    end

    def combine a, b
    return b.size.zero? ? a : b if a.first.nil? || b.first.nil?
    smallest = a.first <= b.first ? a.shift : b.shift
    return combine(a, b).unshift(smallest)
    end

    a = [6,23,53,1,2,5,62,61,33,21,14,6,23].shuffle
    puts "#{merge_sort(a)}"