Neo & Byte · #1 · Quick sort
This quick sort takes the last value of each part as its pivot. On a sorted array that pivot is always the largest value, so every pass splits off only one value, and the sort makes about n²/2 comparisons, O(n²), instead of O(n log n) on average. A random pivot, or the median of the first, middle and last values, avoids this; insertion sort, by contrast, finishes a sorted array with n − 1 comparisons.
In the VisiGrab app, quick sort runs pivot by pivot, every comparison on screen, and shows why a sorted array is its worst case. App Store · Google Play