Sorting

Sorting is a fundamental algorithm in Computer Science. A sorting algorithm takes a list as the input, and returns a list in an order. It is often the first step in many algorithms, and thus setting the lower bound for complexity.

Definition

Given a list S with N elements, S' = Sort(S) is defined as follows:

• for $0 < i \leq N$, $S_i \leq S_{i+1}$.
• S' is a permutation of S.

Put in Lisp:

(defun is-sorted (lst)
  (cond ((< (length lst) 2) t)
	(t (and (<= (first lst) (second lst))
		(is-sorted (cdr lst))))))

Sorting Algorithms and Complexities

• n is the number of elements
• k is the number of distinct objects

Algorithm	Time Complexity	Space Complexity
Bubble sort	O(n2)	O(n) - in place, O(1) extra space.
Insertion sort	O(n2)	O(n) - in place, O(1) extra space.
Selection sort	O(n2)	O(n) - in place, O(1) extra space.
Merge sort	O(nlogn)	O(n) - O(n) extra space.
Heap sort	O(nlogn)	O(n) - in place, O(1) extra space.
Quicksort	O(n2) - O(nlogn) expected, and with high probability.	O(n) - O(logn) extra space.
Introsort	O(nlogn)	O(n) - O(logn) extra space.
Counting sort	O(kn)	O(kn)