Algorithm | Worst case | Avg case | Best Case | Stable | In-place? |
Bubble sort | O(n2) | O(n2) | O(n2) | Stable | Yes |
Selection sort | O(n2) | O(n2) | O(n2) | Not Stable | Yes |
Insertion sort | O(n2) | O(n2) | O(n) | Stable | Yes |
Merge sort | O(n log n) | Stable | No. Need auxiliary space | ||
Quick sort | O(n2) | O(n log n) | Not stable | Yes | |
Heap sort | O(n log n) | O(n log n) | Not stable | Yes |
To check
Boyer Moore Algorithm for Pattern Searching
Masters theorem
Books to read
Algorithm Design By Jon Kleinberg And Eva Tardos
Elements of programming interviews
Leave a Reply