Sorting Algorithms

merge_sort.rb

#!/home/suganya/.rvm/rubies/ruby-2.4.1/bin/ruby
require "byebug"

module MergeSort
  def self.partition(array)
    if array.length == 0
      return []
    elsif array.length == 1
      return array
    end

    mid_element_index = (array.size / 2) - 1

    left_sub_array = array[0..mid_element_index]
    right_sub_array = array[mid_element_index+1..array.length]

    left_sub_array = partition(left_sub_array)
    right_sub_array = partition(right_sub_array)

    result = merge(left_sub_array, right_sub_array)

    result
  end

  def self.merge(left_sub_array, right_sub_array)
    left_index = 0
    right_index = 0
    merged_array = []

    while left_index < left_sub_array.size && right_index < right_sub_array.size
      if left_sub_array[left_index] < right_sub_array[right_index]
        merged_array << left_sub_array[left_index]
        left_index += 1
      else
        merged_array << right_sub_array[right_index]
        right_index += 1
      end
    end

    while left_index < left_sub_array.size
      merged_array << left_sub_array[left_index]
      left_index += 1
    end

    while right_index < right_sub_array.size
      merged_array << right_sub_array[right_index]
      right_index += 1
    end

    return merged_array
  end
end

array = [9,7,3,10,2,1]
result = MergeSort.partition(array)

quick_sort.rb

#!/home/suganya/.rvm/rubies/ruby-2.4.1/bin/ruby

module QuickSort
  def self.sort(array)
    if array.size == 0
      return []
    elsif array.size == 1
      return [array[0]]
    end

    pivot_index = array.size / 2
    pivot = array[pivot_index]

    left_array = array.select{ |elem| elem < pivot }
    right_array = array.select{ |elem| elem > pivot }

    puts "left_array - #{left_array}"
    puts "pivot - #{pivot}"
    puts "right_array - #{right_array}"

    sorted_left = QuickSort.sort(left_array)
    sorted_right = QuickSort.sort(right_array)

    result = sorted_left + [array[pivot_index]] + sorted_right

    puts result
    puts "\n"

    return result
  end
end

array = [1, 100, 55, 2, 44, 3, 10, 4, 120, 130, 15, 36, 40]
result = QuickSort.sort(array)
puts result.join(',')