## Insertion Sort

- Sort the first k numbers.
- Insert k+1’st number v in the proper place.
- Compare v with first k numbers from back to front.
- Stop if find number < v.

### Pseudocode

### Complexity

- Let n = length(A).
- Total number of swaps at most (worst case)
- $1+2+…+(n-1)=n*(n-1)/2 = O(n^2)$.

### Pros and Cons

- 需要一个单位的额外空间来交换
- 对于较小的输入速度较快(n<=20)
- However, not practical for large input size because $O(n^2)$ is too high.

## Mergesort

- Sort an array of numbers
- Divide the array into 2 equal size subarrays.
- Recursively sort each subarray.
- If array size = 1, just return the array.

- Merge two sorted subarrays into one sorted array.
- Key is how to merge efficiently.

### Pseudocode

### Complexity

- Mergesort’s main drawback is need for extra storage in L, R.
- Sorting n numbers requires 2n storage.
- Define
- S(n) = time to mergesort n numbers. = 2S(n/2) + T(n).
- T(n) time to merge two sorted arrays of n/2 numbers.

- T(n) = O(n)
- S(n) = O(nlogn)

## Quicksort

- To sort an array of n numbers, first choose a pivot element x from the array.
- Different ways of choosing pivot.
- Choice of pivot affects performance.

- Move all array elements ≤ x before x, and all elements > x after x.
- Called partitioning.

- Recursively sort each side of x.
- If a side has 0 or 1 elements, don’t recurse.

- Now entire array is sorted.

### Pseudocode

### Complexity

Quicksort’s complexity depends on how balanced the pivot is.

- Say the parts have sizes u, v.
- Perfectly balanced if u = v.

Let S(n) = time to quicksort n numbers.

S(n) = S(u) + S(v) + cn.

**Best case** u = v.

- S(n) ≤ 2 S(n/2) + cn.
- Because u+v = n-1, so u=v=(n-1)/2.

- Solves to S(n) = O(n log n).
- In best case, Quicksort as fast as mergesort.

**Worst case** u = n-1, v=0 (or vice versa).

- S(n) = S(n-1) + cn.
- Solves to S(n) = O(n 2 ).
- Worst case as bad as insertion sort.

## Comparison

### Insertion Sort vs. Mergesort

For large n, mergesort is much faster.

However, for small n insertion sort has less overhead and is very efficient.

Can combine mergesort and insertion sort.

- Divide problem into small groups (≈ 20 elements each).
- Use insertion sort to sort each group.
- Combine the sorted groups using merge.

### Mergesort vs. Quicksort

Unlike mergesort, it doesn’t use any additional storage.

Quicksort spends more time finding a “nice” division of the problem, to make the combination step faster.

Mergesort | Quicksort | |
---|---|---|

Divide array in two parts. | Trivial | O(n) |

Recursively sort each part. | 2S(n/2) | 2S(n/2) |

Combine parts. | O(n) | Trivial |

**Even if partitions are partially balanced, quicksort is fast.**

- Say partitions are 90% imbalanced, i.e. u=0.9n, v=0.1n
- Then S(n) ≤ S(0.9n) + S(0.1n) + cn.
- Even in this case, S(n)=O(nlogn)!

#### Divide and Conquer

- Divide the problem into smaller pieces.
- Solve each recursively.
- Combine the subsolutions into a complete solution

## Resources

Visual Sorting

Example Code

https://github.com/kiki0805/Basic-Algorithm/tree/master/sorting