Sorting

I always get confused with the sorting algorithms. In this document I try to build mental models to remember what each of these sorting algorithms mean.

1. Merge Sort - Splits everything and then merge back while sorting.
2. Quick Sort - Sorts values quickly as soon as it comes across them.
3. Insertion Sort - We take one value and keep checking if there is any better spot for it. Then insert it at that location.
4. Selection Sort - We pick a spot, then select the best possible value for it.
5. Count Sort - In the first pass, we count all available elements and its number of occurrences. Then we update the values in sorted sequence in the original array.

Sorting Algorithm Implementation

Merge Sort

1. Nothing is really merged. Everything is just managed using indexes on same array.
2. Definitely additional memory needed. Half of the size of the array.
3. Mid element is calculated and elements before and after that are sorted.

Quick Sort

1. No additional memory required.
2. Pivot chosen - Always the last element. Or take any random element. But swap that with the last element.
3. Partition - This is just comparing each element from left side with the pivot element value. If the value is smaller, keep moving values to partition start pointer.
4. Once all values until the one before the pivot element is checked, we move the pivot element to the position next the current partition pointer.

Points to remember

• Pivot always last element.
• Partition's first element always 1 lesser than the first element.
• Partition provides the fix value of the element when the partition is completed.
• Further partitions shouldn't consider the previous partition element. Since it's final position is already fixed.