def merge_sort(arr)
def merge_sort(arr)
Base case - since we can’t divide
an array any further once its size
is less than two, just return arr
.
return arr if arr.size < 2
Find the middle point of the array so we can recurse the left and right sections of the array.
middle = arr.size / 2
Recurse the left portion of the array.
Notice we’re using the ...
range when
slicing arr
- this excludes the
end value.
left = merge_sort(arr[0...middle])
Recurse the right portion of the array.
right = merge_sort(arr[middle..arr.size])
Make a call to the merge
function, which
will do the sorting.
merge(left, right)
end
def merge(left, right)
When sorting the values we need to push them into this this variable.
sorted = []
Loop through the left and right arrays.
while left.any? && right.any?
If the first element is greater than or equal
to the first right
element then remove the first
element from the right
array and push it onto the
end of the sorted
array. Otherwise, remove the
first element from the left
array and push it
onto the end of the sorted
array.
if left.first >= right.first
sorted.push right.shift
else
sorted.push left.shift
end
end
Finally, any remaining elements on the left
or right
arrays should be concatenated onto
the sorted
array.
sorted + left + right
end