Computer Science‎ > ‎

### 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]    }    enddef 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)endoriginal_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: