ACO 101 Study Guide - Final Guide: Merge Sort, Quicksort, The Algorithm
Document Summary
So far, we discussed two sorting algorithms: selection sort, which is o(n2), and merge sort, which is o(n log n). However, neither of them is used when you have to sort databases with millions of examples. Instead, the most popular solution in practice is quicksort. The basic idea of the algorithm is that of divide and conquer: we want to partition the array into two parts, sort each one (recursively, of course), and then get the result. But unlike merge sort, where getting the result means the extra work of merging, here we want to just have the result when the recursive calls are nished. The algorithm will work in place, which means that no new array or data structure is created. All the work takes place in the same array, with only o(1) temporary extra memory being allocated. This is a big advantage if you want to handle lots of data. The pseudocode of the algorithm is as follows:
