Basic Data Structures in Ruby - Merge Sort

The Merge Sort is a popular O(n log n) sorting algorithm, which has been discussed in detail, with examples and C code over here :Arrays and Sorting: Merge Sort ( with C Program source code). Over here, we will take a quick look at the Ruby implementation of Merge Sort.

def mergeArrays(arr,start_1,end_1,start_2,end_2)

temp = Array.new(end_1 + end_2 - start_1 - start_2 + 2)
index_1 = start_1 # Marks the index in the first sub-array, which needs to be put into the temporary array next
index_2 = start_2 # Marks the index in the second sub-array, which needs to be put into the temporary array next
index = 0   # Mark the index in the Temporary array which is being filled

  while ( index_1 <= end_1 ) || ( index_2 <= end_2 )

  if ( index_1 <= end_1 ) && ( index_2 <= end_2 ) && (arr[index_1] < arr[index_2] )
temp[index] = arr[index_1]
index += 1
index_1 += 1
  elsif ( index_2 <= end_2 )
temp[index] = arr[index_2]
index += 1
index_2 += 1
  else
temp[index] = arr[index_1]
index += 1
index_1 += 1
  end
  end


  (0..(index-1)).each{ |x|
arr[x + start_1] = temp[x]
  }

end

def mergeSort(arr,startIndex,endIndex)
  return if endIndex <= startIndex
length = endIndex - startIndex + 1
mergeSort(arr,startIndex,startIndex + length/2 -1)
mergeSort(arr,startIndex + length/2 , endIndex)
mergeArrays(arr,startIndex,startIndex + length/2 -1,startIndex + length/2 , endIndex)
end

original_array=[2,19,5,4,3,14,2]
puts "Sorted Array Using Merge Sort:"
mergeSort(original_array,0,original_array.length - 1)
p original_array

Output:

Sorted Array Using Merge Sort:

[2, 2, 3, 4, 5, 14, 19]

Check out some of our other Ruby Tutorials :

Introduction to Ruby

Introduction to Ruby and some playing around with the Interactive Ruby Shell (irb) Introduction to Ruby - Conditional statements and Modifiers: If-then, Unless, Case Introduction to Ruby Comments - Single and Multi-Line comments Introduction to Ruby Loops - Using While, Until, For, Break, Next , Redo, Retry
Introduction to Ruby - Arrays - Sorting, Filtering (Select), Transforming, Multi-Dimensional Arrays Introduction to Ruby - Strings Introduction to Ruby - Making a Script Executable Introduction to Ruby - Regular Expressions, Match, Scan
Introduction to Ruby - Computing Factorials Recursively : An Example of Recursion Introduction to Ruby - Binomial Coefficients (nCr) : An Example of Recursion Introduction to Ruby - Computing a Power Set : An Example of Recursion Introduction to Ruby - Towers of Hanoi : An Example of Recursion
Introduction to Ruby - Strings: Substitution, Encoding, Built-In Methods

Basic Data Structures With Ruby

Basic Data Structures in Ruby - Insertion Sort Basic Data Structures in Ruby - Selection Sort Basic Data Structures in Ruby - Merge Sort Basic Data Structures in Ruby - Quick Sort Functional Programming with Ruby
Basic Data Structures in Ruby - Stack Basic Data Structures in Ruby - The Queue Basic Data Structures in Ruby - Linked List - ( A Simple, Singly Linked List) Basic Data Structures in Ruby - Binary Search Tree