# 算法基础笔记0x02 —— 排序

## 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.

### 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.

### 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.

### 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.

1. Divide problem into small groups (≈ 20 elements each).
2. Use insertion sort to sort each group.
3. 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