Technical Interview Questions: Notes on Sorting and searching algorithms

This is a cheat sheet of sorting algorithms concept. It helps to answer the questions on phone interviews. This sheet explains the key difference between different sorting algos.

Sorting

If the no. of elements are small then we can use quadratic algo like: insertion sort
If there are more then 100 elements use: Heapsort, merge sort, quicksort
For items over: 5,000,000 we can use external memory sorting algorithms.
Stable algos maintains ordering in case of duplicates
Nlogn algos are not stable
If the data is partially sorted then insertion sort is better
If the data is uniformly or randomly distributed then bucket or distribution sort makes sense.
If the keys are long strings then it will make sense to use prefix for the intial sort and then use entire key for sorting. Or use Radix sort
If the range of elements is know and it is small. Then we can initialize an n-element bit-vector. Turn on the element that is present. Then scan from L to R and report the true bits.
For sorting requiring using the disk access we can use external sort or

Load the data in a B-Tree and do in-order traversal
Multi-way merge sort

Quicksort optimizations:

Randomize the permutations
b. Median of first, last, and middle element as a the pivot
c. Smaller subsets can use insertion sort. Stop the recursion at the n = 20
d. We use process the smaller partitions before the larger one. This way run-time memory needed will be less. Successive stored calls are at most half as large as the previous one.

Searching

We can use self organizing list, where the most recently accessed elements moves to the front.
The self organizing list can be used when we have multiple access.