sorting_cheatsheet.rb

#######################
Sorting: http://bigocheatsheet.com/
#######################
Quicksort: 
Time Complexity: best O(nlogn), avg: O nlogn, worst :n^2 (to avoid worst use randomized pivot points)
Space Complexity: O(logn)
Randomly select pivot in a list, move all values lower than pivot to a left list, all values higher to right list.

Heapsort: 
Time Complexity: best O(nlogn), avg: O(nlogn), worst: O(nlogn)
Space Complexity: heap sort takes O(1) extra space
Maintains an array which represents the heap and hence is able to do in place sorting.

Insertion Sort:  
Time Complexity: Best O(N), avg: O(N^2), worst: O(N^2)
Space Complexity: O(1) extra space
Keep sorted input list on left. Take an item from right list and repeatedly swap values until it reaches the right place.(use when most of the elements are sorted).

Mergesort: 
Time Complexity: best o(nlogn), avg: o(nlogn), worst: o(nlogn)
Space Complexity: O(N) extra space
First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.
Merge sort is often preferred for sorting a linked list.