LISP - Sort Sequence

Modern Lisp: Sorting Sequences

Sorting is a fundamental operation in programming. Common Lisp provides a powerful and versatile sort function that can operate on any sequence—a category that includes both lists and vectors. Understanding how to use sort effectively is key to writing efficient and clean Lisp code.

The sort and stable-sort Functions

Important: Destructive Operation

The most critical thing to remember about sort is that it is destructive. It modifies the original sequence in place to save memory. If you need to preserve the original sequence, you must sort a copy.

;; To sort a list non-destructively, use COPY-LIST
(sort (copy-list original-list) #'<)

;; To sort any sequence (list or vector) non-destructively, use COPY-SEQ
(sort (copy-seq original-sequence) #'<)

Syntax

(sort sequence predicate &key key)

• sequence: The list or vector to be sorted.
• predicate: A two-argument function that returns true if the first argument is “less than” the second. Common predicates are < for numbers and string< for strings.
• :key (Optional): A one-argument function that is applied to each element before it is passed to the predicate. This is used for sorting complex objects based on a specific attribute.

Example 1: Sorting a Simple List of Numbers

Here, we sort a list of numbers in ascending order. Notice we copy-list to keep the original intact.

main.lisp

(defparameter *numbers* '(4 3 7 2 1 8 3))

;; Sort a COPY of the list, leaving *numbers* untouched.
(defparameter *sorted-numbers* (sort (copy-list *numbers*) #'<))

(format t "Original: ~a~%" *numbers*)
(format t "Sorted:   ~a~%" *sorted-numbers*)

Output

Original: (4 3 7 2 1 8 3)
Sorted:   (1 2 3 3 4 7 8)

Example 2: Sorting a Vector of Strings with stable-sort

stable-sort is like sort, but it guarantees that the relative order of elements that are considered equal by the predicate is preserved. This can be important in certain algorithms. Here we use string-lessp for case-insensitive comparison.

main.lisp

(defparameter *strings* #("Lisp" "Python" "lisp" "Java"))

;; Use string-lessp for case-insensitive sorting.
(defparameter *sorted-strings*
  (stable-sort (copy-seq *strings*) #'string-lessp))

(format t "Original: ~a~%" *strings*)
(format t "Sorted:   ~a~%" *sorted-strings*)
;; Note: "Lisp" comes before "lisp" in the output because stable-sort
;; preserves their original relative order.

Output

Original: #("Lisp" "Python" "lisp" "Java")
Sorted:   #("Java" "Lisp" "lisp" "Python")

Example 3: Sorting a List of Objects with a :key

The :key argument is extremely powerful. Let’s sort a list of sublists (representing people and their ages) based on the age (the second element).

main.lisp

(defparameter *data* '(("Alice" 30) ("Bob" 25) ("Charlie" 35)))

;; The :key #'second tells sort to extract the second element
;; of each sublist before comparing them with <.
(defparameter *sorted-data* (sort (copy-list *data*) #'< :key #'second))

(format t "Sorted by age: ~a~%" *sorted-data*)

Output

Sorted by age: (("Bob" 25) ("Alice" 30) ("Charlie" 35))

Common Pitfalls and Best Practices

• Modifying Literals: Never try to sort a quoted literal like (sort '(3 2 1) #'<). This attempts to modify constant data and results in undefined behavior, which can crash your program. Always sort a fresh or copied sequence.
• Performance: Sorting a vector is generally faster than sorting a list due to better memory locality. If performance is critical, consider converting your list to a vector before sorting: (coerce my-list 'vector).