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

Linear time sorting #

Counting sort #

Radix sort #

Bucket sort #