Search code examples
sortingmergesortinsertion-sortclisp

Sorting in Clisp

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.

Solution

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

    http://en.literateprograms.org/Merge_sort_(Lisp)

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

    http://en.literateprograms.org/Insertion_sort_(Lisp)

    But loops can easily be turned into tail recursion instead.