These two lines:
merge_sort(left)
merge_sort(right)
should be:
left = merge_sort(left)
right = merge_sort(right)
Since your merge sort is not sorting in place, you need to assign the result back to the variables.
Frage
Can anybody please tell what am I doing wrong in my Merge-Sort
def print_array(a)
print a
print "\n\n"
end
#Merge-Sort code starts Here.
def merge_sort(a)
if a.size < 2
return a
end
middle = (a.length / 2).to_i
left = a.slice(0, middle)
right = a.slice(middle, a.size)
merge_sort(left)
merge_sort(right)
a = merge(left, right)
end
def merge(left, right)
result = []
while left.length > 0 || right.length > 0
if left.length > 0 && right.length > 0
if left[0] <= right[0]
result << left.slice!(0)
else
result << right.slice!(0)
end
elsif left.length > 0
result.concat left.slice!(0..left.length-1)
elsif right.length > 0
result.concat right.slice!(0..right.length-1)
end
end
result
end
a = [ 3, 2, 1 ]
print_array(a)
a = merge_sort(a)
print_array(a)
Basically, What I know is that when it comes time to Merge [2] and [1], that happens correctly (ie. [1, 2] is returned) , but for the previous step of the Recursion as it unwinds, it comes back (or doesn't come back) as [1, 2] but as [2, 1], ie.
Previous step -> left = [3] -> right = [2, 1] #This is the value of right from recursion instead of [1, 2]
I don't know how to fix this, and it's driving me crazy, Can you please help me?
Lösung
These two lines:
merge_sort(left)
merge_sort(right)
should be:
left = merge_sort(left)
right = merge_sort(right)
Since your merge sort is not sorting in place, you need to assign the result back to the variables.