Mergesort and Quicksort with Dynamic Languages

The other day I was flipping through an algorithms book and came across a section on sorting. I remembered that I had a blast writing them c++ during my undergrad and thought it would be fun to write them in a couple of different languages. I settled on writing a quicksort, and mergesort. Interesting notes:

1. Python(2.5) returns a None type when appending a value to an empty list which forced me to use ‘+’

    > ex= [].append()
    > print ex
    > None

2. Groovy gave me a java.util.ConcurrentModificationException when I transcribed my Ruby code to Groovy. Because of the fact that I was deleting items from a list that I would read in later(while loop which checks size of left and right), I got this error. Accounting for that, the groovy code is pretty nasty.(anyone that would like to provide a better example without relying on the built in Collections.sort(list) would be welcome)

Here is my code… enjoy!

# javazquez.com
#==========MERGE SORT========

#-------------RUBY----------------

def merge_sort(ary)
  return ary if (ary.length <= 1)
  half = ary.length/2
  left = merge_sort(ary[0...half])
  right = merge_sort(ary[half..ary.length-1])
  result =[]
#compare first left and first right
  while left.length > 0 and right.length > 0
    result << (left[0] < right[0] ? left.shift : right.shift)
  end
  result.concat((left.length > 0 ? left : right))
  return result
end

ary=[1,5,14,3,2,45,2,0,01,-1]
p merge_sort(ary)

#-----------Python Mergesort-------------

def merg_sort(lst):
    if(len(lst) <= 1):  return lst
    left = merg_sort(lst[:len(lst)/2])
    right = merg_sort(lst[len(lst)/2:len(lst)])
    result = []
    while len(left) > 0 and len(right)> 0:
        if( left[0] > right[0]):
            result.append(right.pop(0))
        else:
            result.append(left.pop(0))

    if(len(left)>0): result.extend(merg_sort(left))
    else: result.extend(merg_sort(right))

    return result

print merg_sort([8,7,43,2,5])

--------Erlang Mergesort-------------
-module(mergesort).
-export([ms/1,msTestSuite/1]).

ms(Lst)->break(Lst).
break([]) -> [];
break([L]) -> [L];
break(List) ->
    {Left, Right} = lists:split(length(List) div 2, List),
    merge(break(Left),break(Right)).

merge(L, []) -> L;
merge([], R) -> R;
merge([Lh|Ltail],[Rh|Rtail])->
	 if
	 Lh < Rh -> [Lh | merge(Ltail,[Rh|Rtail])];
	 Lh >= Rh -> [Rh | merge(Rtail,[Lh|Ltail])]
	 end.

%to test, run mergesort:msTestSuite(run).
msTestSuite(run)->
	[mstest1(run),mstest2(run),
	mstest3(run),mstest4(run),
    mstest5(run)].

mstest1(run)-> ms([3,2,1]).
mstest2(run)-> ms([3,3,3,1]).
mstest3(run)-> ms([]).
mstest4(run)-> ms([1]).
mstest5(run)-> ms([123,0,-1,23,2,34,5,678,7,5,8]).

//-------------GROOVY MERGESORT--------
def ms(lst){
    if(lst.size() <= 1){return lst}
    def sz=lst.size()
    int half = (int)(sz/2)
    def l = lst [ 0 .. < half]
    def r = lst [ half.. < sz]
    def lft = ms(l)
    def rht  = ms(r)
    def result = []
    def rcnt = 0
    def lcnt = 0
   while( lcnt < lft.size() && rcnt < rht.size()){
        if(lft[lcnt] < rht[rcnt]){
        	result += lft[lcnt++]
		}
        else{
			result += rht[rcnt++]
		}
     }
    if(lcnt < lft.size()){
		result +=  ms(lft[lcnt..< lft.size()])
	}
    else{
		result += ms(rht[rcnt..< rht.size()])
	}
    return result
}

sl=[3,88,5,3,2,1,-2,2]
println ms(sl)

# javazquez.com
#========QUICKSORT========

#-----RUBY----------------
def quick_sort(ary)
  return ary if(ary.length <= 1)
  greater,less = [],[]
  pos = rand(ary.length)
  pivot = ary[pos]
  ary.delete_at(pos)
  ary.each{|item|
       (item < pivot) ? less << item :greater << item}
  return (quick_sort(less) << pivot).concat(quick_sort(greater))
end

ary=[1,5,14,3,2,45,2,0,01,-1]
p quick_sort(ary)

#----------Python Quicksort--------------

import random
def quickSort(lst):
	if(len(lst) <= 1):return lst
	greater = []
	less = []
	pivot = lst.pop(random.randint(0,len(lst)-1))
	for item in lst:
		if(item < pivot): less.append(item)
		else: greater.append(item)
	return quickSort(less)+[pivot]+quickSort(greater)

ary=[1,5,14,3,2,45,2,0,01,-1]

----------Erlang Quicksort--------------
-module(quicksort).
-export([qsort/1]).

qsort([]) ->[];
qsort([Pivot|T]) ->
		lists:append( [qsort([X || X <- T, X < Pivot]),
		[Pivot], qsort([X || X <- T, X >= Pivot]) ).

-------GROOVY QUICKSORT--------------
def quickSort(lst){
	if(lst.size() <= 1){return lst}
	def greater = []
	def less = []
	def pivot = lst.remove(new  Random().nextInt(lst.size()))
	lst.each{item->
		if(item < pivot){ less.add(item)}
		else{greater.add(item)}
	}
	return quickSort(less)+[pivot]+quickSort(greater)
}
print quickSort([1,5,14,3,2,45,2,0,01,-1])