Take the 2-minute tour ×

So... I want to write an insertion sort and a merge sort in clisp. The input will be a flat list of numbers. How would one write these 2 sorts recursively (preferably without using lambdas)? For the insertion sort I was thinking of making a function that takes the list and an integer (which is meant to be the current index of the element of interest) as arguments, and using setf and nth to manipulate the list. I know there's also supposed to be another recursive function inside that one, but like... I just get confused with so many functions and variables to store and stuff.

For merge sort I have absolutely no idea.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

Merge sort is naturally recursive (as is any divide and conquer problem)


The insertion sort implementation they have cited is sort of anti-functional


But loops can easily be turned into tail recursion instead.

share|improve this answer
Not that Common Lisp is guaranteed to be tail recursive, but most implementations do that as an implementation detail. –  Will Hartung Mar 11 '12 at 0:03
The merge looks okay, but the insertion one is a bit... crazy. This is precisely why I came here--I have no clue what any of that looping syntax or "finally", or "aref", or "1+/1-", or "flet" stuff is. –  Pojo Mar 11 '12 at 21:57

Your Answer


