# Sorting

Calculate the permuation that orders the elements in an array.

## Insertion sort #

**Idea**: Start with one element, keep adding new elements and swap them until they have the right position.

- Worst case: $\mathcal{O}(n^2)$
- Base case: $\mathcal{O}(n)$
- Average case: $\mathcal{O}(n^2)$
- In-place

## Merge sort #

Uses the recursive divide and conquer approach:

**Divide**the problem into subproblems**Conquer**the subproblems by recursion**Combine**the solutions of the subproblems into the global solution

**Idea**: Split array into two parts which get sorted recursively (devide/conquer) and merge the two sorted subarrays into a full array (combine)

- Time complexity: $\Theta(n \lg n)$
- Needs additional memory

## Quicksort #

## Heap sort #

- Construct a heap in linear time
- Get items from the top of the heap untill it is empty