# Sorting

 Sorting Algorithms Bubble sort Insertion sort Selection sort Quicksort Merge sort Heap sort Introsort Counting sort Problems Problems solvable using 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)