## Merge Sort in Ruby

Merge sort is one of the fundamental sorting algorithms used in computer science. It belongs to the divide and conquer category of algorithms, where a problem is divided into smaller sub-problems that are solved recursively. In this blog post, we’ll explore merge sort in-depth, focusing on its implementation in Ruby.

## What is Merge Sort?

Merge sort operates by dividing an array into two halves, sorting each half separately, and then merging the sorted halves back together. It follows the divide and conquer strategy to efficiently sort large datasets.

## The key steps of the merge sort algorithm can be summarized as follows:

Divide the unsorted array into two halves. Recursively sort each half. Merge the sorted halves back together. Ruby Implementation: Now, let’s delve into the implementation of merge sort in Ruby:

```
def merge_sort(arr)
return arr if arr.length <= 1
mid = arr.length / 2
left_half = merge_sort(arr[0...mid])
right_half = merge_sort(arr[mid..])
merge(left_half, right_half)
end
def merge(left, right)
sorted_arr = []
until left.empty? || right.empty?
if left.first <= right.first
sorted_arr << left.shift
else
sorted_arr << right.shift
end
end
sorted_arr + left + right
end
# Example usage:
arr = [3, 7, 2, 8, 1, 9, 5, 4, 6]
sorted_arr = merge_sort(arr)
puts sorted_arr.inspect
```

## Here’s a breakdown of what each part of the code is doing:

The function `merge_sort(arr)`

is the main function that implements the merge sort algorithm. It first checks if
the array has a length of 1 or less. If it does, there’s no point in sorting it, so it returns the array.
If the array has more than one element, it finds the midpoint of the array, splits the array into two halves at
that point, and then recursively calls `merge_sort`

on each half.
The `merge(left, right)`

function is handling the actual merging of the sorted sub arrays. It creates an empty
array `sorted_arr`

, and then in a loop, it continuously removes the smallest element from the first position of
the left or right array and adds it to sorted_arr. This process continues until one of the arrays is empty.
At the end, it concatenates any remaining elements from left or right to `sorted_arr`

, and returns it.
Finally, in the example usage, you create an array `arr`

, call `merge_sort(arr)`

, and put the result in `sorted_arr`

,
which you then print.