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.

Ascending and descending

There's one rule that's followed in all sorting algorithms to switch between ascending and descending sorting. The rules are

1. If 'a' must come before 'b' then return $-1$.
2. If 'b' must come after 'a' then return $+1$.
3. If 'a' and 'b' are equal then return $0$.

We can write the code as below to achieve ascending and descending orders using the rules stated above..

// Ascending
(a, b) -> {
    if (a < b) return -1; // a comes before b.
    if (a > b) return 1; // a comes after b.
    return 0;
}

// Descending
(a, b) -> {
    if (a > b) return -1; // a comes before b (same as above)
    if (a < b) return 1; // a comes after b (same as above)
    return 0;
}

The subtraction version is just a shorthand of the logic above but uses a clever idea. This ensures the returned value is $-1$ or $+1$ based on the way

how subtraction is mapped to the above logic

If the subtraction results in any negative value (not just $-1$), then first argument comes before second. If the subtraction results in positive value (not just $+1$), then first argument comes *after+ second.

The idea holds good for everything including sorting just negative numbers too.

Arrays.sort(arr, (a, b) -> a - b); # Ascending
Arrays.sort(arr, (a, b) -> b - a); # Descending

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.