Quick Sort
Learn Quick Sort (Sorting, Data Structures & Algorithms) with worked examples, diagrams and interview questions. Free on JavaSchoolLab.
Quick Sort - O(n log n) Average, In-Place Picks a PIVOT, partitions the array so everything smaller is to its left and everything bigger is to its right, then recursively sorts each side. Unlike Merge Sort, partitioning happens IN-PLACE - no auxiliary array needed for the main work. Average case O(n log n) , but worst case O(n²) when the pivot repeatedly splits badly (e.g. always picking the smallest/largest element, as happens on an already-sorted array with a naive "always pick the last element" pivot rule). In-place - O(log n) extra space for the recursion stack, no auxiliary array....