oaktree

Merge Sort - Ruby

Mar 22nd, 2016
94
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #! /usr/bin/env ruby
  2. class Array
  3.     def mergesort
  4.  
  5.         return self if length <= 1
  6.        
  7.         if length == 2 # we swap if the length is two and the "two array" is unsorted still
  8.             if (self[0] > self[1])
  9.                 self[0],self[1] = self[1],self[0]
  10.             end
  11.  
  12.             return self
  13.         end
  14.  
  15.         left = self[0...self.length/2].mergesort
  16.         right = self[self.length/2...self.length].mergesort
  17.  
  18.         arr = []
  19.  
  20.         while(!left.empty? && !right.empty?)
  21.             if left.first < right.first
  22.                 arr << left.first
  23.                 left.shift #i remove the first element from left after it gets merged
  24.                 # it's so i can keep comparing using left/right.first
  25.             else
  26.                 arr << right.first
  27.                 right.shift # remove first element from right after merging it
  28.             end
  29.         end
  30.  
  31.         if !left.empty?
  32.             arr += left # if the left array is not yet fully merged, tack on the remaining values
  33.         elsif !right.empty?
  34.             arr += right # if the right array is not yet fully merged, tack on remaining values
  35.         end
  36.  
  37.         return arr
  38.     end
  39. end
  40.  
  41.  
  42.  
  43.  
  44. puts "give me a string"
  45. str = gets.chomp.split('')
  46. strlen = str.length
  47. puts str.mergesort.join('')
RAW Paste Data