Sorting algorithms

O(n ^ 2) runtime

0. Bubble Sort
1. Insertion Sort

O(n logn) runtime
0. merge sort
1. quick sort
2. heap sort

O(n) run time

0. counting sort
only work for integers. we will need to know the largest integer, L. sorting is done O(n). Create an array with size equal to maximum number of the sequence to be sorted. The traverse through the sequence and count the occurrence of each number. Finally, fill the initial array with the count.
Algorithm:
def count_sort(A):
  L = MAX_INTGER_IN_LIST
  count = [0] * L

  for num in A:
    count[num]++

  index = 0

  for i in range(0, A.len):
    c = count[i]
    for k in range(index, index+num):
      A[k] = i
  return A

Order: O(num_elements + max_integer). this comes from the two for loops.

1. radix sort
k = log_10(MAX_NUM_IN_SEQUENCE) + 1 gives the number of digit required to represent a number in 10 based system.

def radix_sort(A):
    max_digit = log(MAX_INTEGER, 10) + 1
    #create 10 buckets

    for dig_index in range(0, max_digit):
      bucket = [[]] * 10
      divisor = pow(10, dig_index)
      for number in A:
        n = number / divisor
        digit = n % 10
        bucket[digit].append(number)
      A.clear()
      for list in bucket:
        for num in list:
          A.append(num)
    return A

This algorithm is stable if it maintains order of input elements. The radix sort maintains the order of previous elements, that's why it works.

123, 153, 117
first round: 3, 3, 7
123
153  //order maintained
117

second round: 2, 5, 1
117
123
153

third round: 1, 1, 1
order maintained.

The last round shows an example of stability. Because all the digits are the same, the algorithm does not alter any number in the sequence.