# Sort

## Comparison sort

- Determine the sorted order of an input array by comparing element.
- Using decision-tree model, we prove a lower bound of $\Omega (n \log n)$ on the worst-case running time of any comparison sort on n inputs
- Ex: Insertion sort, Merge sort, Heapsort, quicksort
- Best TC = O(n log n)

### Insertion sort

- TC= $O(N^2)$, SC= $O(1)$, inplace
- For loop the arr from left to right
- For each iteration, we want to relocate the current value arr[i] to the right place. The action we do is to compare the current value arr[i] with the previous one arr[i - 1], if arr[i] < arr[i - 1], swap them. Doing the action until we do not have to swap the values.
- In ith iteration, it takes $O(i)$ time complexity to put the arr[i] into the right place.

### Merge sort


- TC= $O(N\logN)$, SC= $O(N)$, Divide & Conquer, NOT inplace!!
- The divide step: split the arr into two subarrays.
- It grows a binary tree with $O(\log N)$ height.
- The conquer step: merge two sorted subarrays
- For each layer of the binary tree, it takes $O(N)$ time complexity to merge subarrays.

### Heapsort


- TC= $O(N\logN)$, SC= $O(1)$, inplace.
- Use the (binary) heap data structure to complete sorting.
- min heap: the parent val < the children vals
- binary heap = binary complete tree -> no null value in arr
- The heap step: make the arr satisfy with the heap property using heap-insert operation for each value from left to right.
- One heap-insert operation takes $O(\log i)$, so the entire heap step takes $O(N\log N)$.
- The sort step: for ith iteration, swap arr[i] with arr[len(arr) - i - 1], then do heapify in arr[i: len(arr) - i - 2].
- One heapify operation takes $O(\log i)$, so the entire sort step takes $O(N\log N)$.

## Counting sort

- Beat this lower bound of $\Omega (n \log n)$ if we can gather information about the sorted order of the input.
- Ex: Counting sort, Radix sort, Bucket sort

## In-place sort
- Insertion sort
- heapsort

## Stable sort

## Unstable sort