Sorting in functional programming languages

Here are some links to sorting algorithms implemented in Haskell:

• Quicksort
• Insertion sort
• Merge sort
• Selection sort
• Counting sort

Merge sort is often the best choice for sorting linked lists. Functional languages usually operates on lists although I have little knowledge on how most functional languages implements lists. In Common Lisp they are implemented as linked lists and I presume most functional languages do as well.

While quicksort can be written for linked lists it will suffer from poor pivot selection because of random access. While this does not matter on completely random input, on partially or completely sorted input pivot selection becomes very important. Other sorting algorithms may also suffer from the slow random-access performance of linked lists.

Merge sort on the other hand works well with linked lists and it is possible to implement the algorithm such that it only requires some constant of extra space with linked lists.

Here's the classic (pseudo-?)quicksort in Haskell:

sort []      =   []
sort (p:xs)  =   sort [x | x<- xs, x <= p]
              ++ [p]
              ++ sort [x | x <- xs, x > p]

See, e.g., c2.com or LiteratePrograms.org. Merge sort isn't much harder to write and more reliable in practice. The same can be done in Scheme with:

(define (sort xs)
  (if (null? xs)
    '()
    (let* ((p (car xs)) (xs (cdr xs)))
      (call-with-values (lambda () (partition (lambda (x) (<= x p)) xs))
                        (lambda (l r)
                          (append (sort l) (list p) (sort r)))))))

with partition from SRFI-1 (untested code). See also chapter 4 of R6RS libraries.

In a functional language you write a function that given a list returns a sorted list, not touching (of course) the input.

Consider for example merge sorting... first you write a function that given two already sorted lists returns a single sorted list with the elements of both in it. For example:

def merge(a, b):
    if len(a) == 0:
        return b
    elif len(b) == 0:
        return a
    elif a[0] < b[0]:
        return [a[0]] + merge(a[1:], b)
    else:
        return [b[0]] + merge(a, b[1:])

then you can write a function that sorts a list by merging the resulting of sorting first and second half of the list.

def mergesort(x):
    if len(x) < 2:
        return x
    else:
        h = len(x) // 2
        return merge(mergesort(x[:h]), mergesort(x[h:]))

About Python syntax:

• L[0] is the first element of list L
• L[1:] is the list of all remaining elements
• More generally L[:n] is the list of up to the n-th element, L[n:] the rest
• A + B if A and B are both lists is the list obtained by concatenation
• [x] is a list containing just the single element x

PS: Note that python code above is just to show the concept... in Python this is NOT a reasonable approach. I used Python because I think it's the easiest to read if you know any other common imperative language.