Merge sort (in Haskell)

March 24, 2009

-- Merge sort
-- Date: Tuesday, March 24, 2009

-- sort a list using merge sort
mergesort [s] =
	[s]
mergesort a =
	let
		mid = ceiling ((fromIntegral (length a))/2)
		(f,s) = splitAt mid a
	in
		merge (mergesort f) (mergesort s)

-- merge two lists
merge :: (Ord t) => [t] -> [t] -> [t]
merge a@(ah:at) b@(bh:bt)
	| ah < bh =
		[ah] ++ merge at b
	| otherwise =
		[bh] ++ merge a bt
-- base case 1: second list empty so we just add everything in a to the end
-- Note: Case [] [] is handled here as well
merge a [] =
	a
-- base case 2: same as above except it is for first list empty
merge [] b =
	b
Advertisements
# Insertion sort
# Date: Tuesday, March 24, 2009

print 'Insertion sort\n'
print 'How many numbers would you like to enter: '
num = input()

print 'Please enter ' + str(num) + ' numbers'

numbers = []
for i in range(num):
    numbers += [input()]

for j in range(1, num):
    key = numbers[j]
    i = j-1
    # Keep shifting elements to the right until the right position is found
    while numbers[i] > key and i >= 0:
        numbers[i+1] = numbers[i]
        i = i - 1
    numbers[i+1] = key
    print(numbers)