Sort

Selection Sort

Time : O(n^2), Space : O(1) (In-place)

def selectionSort(num):
    n = len(num)
    for i in xrange(n):
        min_idx = i
        for j in xrange(i+1,n):
            if nums[j] < nums[min_idx]:
                min_idx = j
        nums[i], nums[min_idx] = nums[min_idx], num[i]

• Follow up : Use Two Stack or Tree Stack sort!

Merge Sort

Follow up

• merge sort a Linked List
• A1B2C3D4 -> ABCD1234
• ABCD1234 -> A1B2C3D4

Quick Sort

Rainbow Sort

abcccabbcbbcbbacaa -> aaaa bbbbb ccccc