Quick sort is of O(n log n) time on average and O(n²) worst case when the array is already sorted.
From Algorithms class: • array rearranged such that, when two subarrays sorted, the whole array is ordered (contra merge where array is broken into 2 subarrays to be sorted and then combined to make whole ordered array) • recursive calls happen after working on whole array • partition/pivot not necessarily in middle (Or necessarily the median value, leading to the worst case performance). • improvements: insertion sort for tiny arrays, median of 3, randomize beforehand • strength: average case N log N, in-place so small usage of memory (small aux stack), shorter inner loop so fast in practice as well • weakness: worst case is quadratic, happens with already sorted array (where pivot = first item) • time efficiency: average & best — O(N log N), worst — O(N^2), small constant factor • To partition, have two pointers at each end working toward each other. Stop pointers when each reaches a value out of place. Swap them. • Usually not stable. • Difference is that in merge sort, the sorting action happens on the way up (when ordered subarrays are merged), whereas in quicksort, the sorting happens on the way down when the (sub)array is split and the low and high elements are separated and the pivot element is placed in its correct final position. • “The difference between the two is basically which linear operation they leverage. Quick Sort is efficient because you can partition a list into items that come before and items that come after a given item in linear time. Merge Sort is efficient because given two already sorted lists you can combine the two, and maintain sorted order, in linear time.”