Merge Sort Algorithm in Ruby

1. Introduction

Merge sort is a divide-and-conquer algorithm that was invented by John von Neumann in 1945. It breaks down a dataset into individual pieces and merges them, using a predefined order, into a sorted list.

2. Implementation Steps

1. Divide the unsorted list into n sublists, each containing one element (a list of one element is considered sorted).

2. Repeatedly merge sublists to produce new sorted sublists until there is only one sublist remaining. This will be the sorted list.

3. Implementation in Ruby Programming

def merge_sort(list)
    return list if list.size <= 1
    mid = list.size / 2
    left = list[0, mid]
    right = list[mid, list.size]
    merge(merge_sort(left), merge_sort(right))
end
def merge(left, right)
    sorted = []
    until left.empty? || right.empty?
        if left.first <= right.first
            sorted << left.shift
        else
            sorted << right.shift
        end
    end
    sorted.concat(left).concat(right)
end
# Client code
arr = [38, 27, 43, 3, 9, 82, 10]
puts "Original array: #{arr}"
sorted_array = merge_sort(arr)
puts "Sorted array: #{sorted_array}"

Output:

Original array: [38, 27, 43, 3, 9, 82, 10]
Sorted array: [3, 9, 10, 27, 38, 43, 82]

Explanation:

1. Merge sort uses the principle of divide and conquer to sort an array. The main idea is to divide the original array into two halves until each sub-array contains a single element.

2. A single-element array is always sorted.

3. The merge process takes place. It takes two smaller sorted arrays and combines them to produce a single sorted array.

4. The merge function compares the elements of both sub-arrays one by one and places the smallest element into the sorted array.

5. This process is recursively applied to all array elements.

6. Once all arrays have undergone merge operations, we get a single sorted array.