3
\$\begingroup\$

I am implementing the algorithms of Course: Coursera Algorithm I. I implemented the Merge-Sort using recursion and although it sorts correctly I am not sure if it is a correct implementation of this algorithm. Could you guys take a look? How can I keep it more "readable"?

##
# Implemetation of Merge Sort see: {https://pt.wikipedia.org/wiki/Merge_sort}
module Merge
  class Sort
    include Validator, Comparator

    def sort(values)
      return values if invalid_to_sort?(values)
      _sort(values, 0, values.size - 1)
    end

    private

    def _sort(values, ibegin, iend)
      return [values[ibegin]] if ibegin == iend

      mid = ((iend - ibegin) / 2) + ibegin

      left  = _sort(values, ibegin, mid)
      right = _sort(values, mid + 1 , iend)

      merge([], left, right)
    end

    def merge(values, left, right)
      # p "values #{values} left #{left} right #{right}"
      return values if left.empty? and right.empty?

      if left.empty?
        merge(values + [right.shift], left, right)

      elsif right.empty? || (left.first <=> right.first) <= 0
        merge(values + [left.shift], left, right)

      else
        merge(values + [right.shift], left, right)
      end
    end
  end
end

The entire implementation

\$\endgroup\$
  • \$\begingroup\$ CodeReview is for already tested code: I do not know if it this is correct sound off-topic \$\endgroup\$ – Caridorc Oct 1 '15 at 17:38
  • \$\begingroup\$ It sorts properly. Just would like to know if I've followed the right path of the algorithm and it's readability. \$\endgroup\$ – Cristian Oliveira Oct 1 '15 at 17:42
  • 1
    \$\begingroup\$ Perfectly on-topic then! Welcome to CodeReview :D \$\endgroup\$ – Caridorc Oct 1 '15 at 17:43
2
\$\begingroup\$

Yes, both methods seem to work correctly, your code definately implements mergesort :).

Your code, however, seems like somewhat direct translation of C implementation, as it hardly uses Ruby idioms, what hurts readability. Ruby Arrays know they size (#length, #empty? etc.), so you don't need to keep track of it. So, splitting the array could very well be done like:

# _sort now only accepts one argument, values
mid = values.length / 2
left = _sort(values[0...mid])

Such approach would of course require you to rewrite #merge, but it would be worth it, as it is more readable to work on actual arrays than criptic numbers. This would also probably eliminate need for Validator module to exist (and Comparator doesn't seem to be used anyways). You should always aim at using idiomatic Ruby, because reader of your code seeing something C-like will waste much time thinking "why didn't <insert idiom> suffice here?" to analyze your code.


If someone passes wierd value to your #sort (like, a Fixnum), it will raise cryptic errors like NoMethodError: undefined method 'empty?'. You should handle such errors by rescueing them and raising more descriptive ones (in this case, ArgumentError probably) so they are easier to analyze. #merge should be handled separately, as NoMethodError there likely means something else.

def invalid_to_sort?(values)
  # I don't think nil deserves special treatment here though, it should
  #   raise ArgumentError like all non-arrays. This seems to come from
  #   C where arrays are pointers and NULL is pointer too, so they are
  #   hard to distinguish without direct check
  values.nil? || values.empty? || values.one?
rescue NoMethodError
  raise ArgumentError, "some descriptive message"
end

Your current code structure introduces somewhat odd (non-Ruby) interface.

sorter = Merge::Sort.new
sorted = sorter.sort(array)

Following example of standard library, Rubyish thing to do would be something like:

array.merge_sort! # destructive
# and
sorted = array.merge_sort # safe

This is easily achieved by making safe variant work on a duplicate:

class Array
  def merge_sort!
    # ... code code code ...
  end

  def merge_sort
    dup.merge_sort!
  end
end

Of course, patching standard classes is dangerous, but as various examples (most notably Rails) prove, also extremely usefull. If you are concerned, you could use refinements , but those are somewhat experimental. However, as you are adding new functionality (and not replacing existing one) only real danger is conflicting with some other patch, so I'd say go for it.

In any case, there is no need to introduce a class, more so one that you need to instantiate. If you want external sorting method (to avoid patching Array), just make it part of a module to keep things simple, i.e:

module Sort 
  def self.merge_sort(values)
    # ... code code code ...
  end
end

sorted = Sort.merge_sort(array)

Now I know from your previous question that you come from Java, so you like to instantiate alot ;) but in Ruby we work somewhat differently, here a module/class is proper object that works like anything else, not some sort ofmetadata-thingy, so it's easy to use them with dependency injection and what-not, usually there is no need to create instances just to call some code :)

\$\endgroup\$
  • \$\begingroup\$ Thanks again!! Your reviews are really helpful I am learning a lot!. I forgot about 'Array#slice'. Those ruby "open" objects are interesting but can turn in a headache. That refinements seem a good option. (btw I refactored the gem using ur advice :D ) \$\endgroup\$ – Cristian Oliveira Oct 2 '15 at 21:53
  • 1
    \$\begingroup\$ Here's an example of a question over on StackOverflow I answered yesterday, introducing some of the scoping features of Refinements: stackoverflow.com/a/32988220/2988 Since you come from the Java world, you are probably familiar with Classboxes? Refinements are heavily inspired by them. \$\endgroup\$ – Jörg W Mittag Oct 8 '15 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.