4

I am new to Ruby and I am trying out the merge sort algorithm as given in Wikipedia

I am getting "comparison of Fixnum with Array failed (ArgumentError)" failed error when comparing the first elements of the left and right array in the merge method. What could be the reason and how do I resolve this problem? Thanks :) 

def mergeSort(array)
    if array.length == 1
        return array
    end

    middle = array.length/2 - 1
    left = array[0..middle]
    right = array[middle+1..array.length-1]

    left = mergeSort(left)
    right = mergeSort(right)
    merge(left,right)
end


def merge(left,right)
    result = []
    while left.length > 0 || right.length > 0
        if left.length > 0 && right.length > 0
            one = left[0]
            two = right[0]
            puts ("one's class is #{one.class} two's class is #{two.class} two is #{two}")
            if one <= two
                result << left.shift
            else
                result << right.shift
            end
        elsif left.length > 0
            result.push(left)
            left = []
        else
            result.push(right)
            right = []
        end 
    end
    puts "result is #{result}"
    result
end
sarnold
  • 102,305
  • 22
  • 181
  • 238
Pramod
  • 5,150
  • 3
  • 45
  • 46

1 Answers1

5

The error is on these lines:

    elsif left.length > 0
        result.push(left)
        left = []
    else
        result.push(right)
        right = []
    end

A simple example should indicate why:

irb(main):067:0> a=[1,2]
=> [1, 2]
irb(main):068:0> b=[3,4]
=> [3, 4]
irb(main):069:0> a.push(b)
=> [1, 2, [3, 4]]

Instead of push(), try concat().

sarnold
  • 102,305
  • 22
  • 181
  • 238
  • 1
    Nice, and that would eventually trigger the error in `one <= two` as you'd have a mixture of Fixnum and Array in the arrays. – mu is too short Nov 13 '11 at 09:05
  • 1
    @mui: That's it exactly. +10 to pramod for posting a complete, testable program -- there's nothing quite like seeing an error message in a REPL loop. :) – sarnold Nov 13 '11 at 09:08
  • @sarnold Thank you :) I will go through the docs more carefully from now on – Pramod Nov 13 '11 at 09:42
  • 1
    @pguardiario, true enough, that would also work. And if Pramod finds that more clear, then he should go with it. But I would find it easier to read `concat()` than `+=` in six months -- I'd wonder if `+=` adds its right argument as a single element (an alias for `push()`) or concatenates lists (an alias for `concat()`). I'd go for clarity every time. If `+=` is more clear to you then go for it. :) – sarnold Nov 13 '11 at 09:45