Introduction to Sorting Algorithms

Quicksort is essentially a divide and conquer algorithm which relies on a partition operation. To partition an array, a pivot is selected. All elements smaller than the pivot are moved before it and all greater elements are moved after it. The lesser and greater sublists are then recursively sorted. The average time complexity of quicksort is O(n log n) and space complexity is O(log n). It is one of the most popular sorting algorithm and its implementation is available in most standard programming libraries.

external merge sort is used when the input data can not fit into the main memory (usually RAM) and instead it must reside in the slower external memory, usually hard disk drive.

Merge sort takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4…​) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list.

Bubble sort starts at the beginning of the data set. It compares the first two elements and if the first element is greater than the second, it swaps them. It continues doing this for each pair of adjacent elements to the end of tje data set. It then starts again with the first two elements, repeating until no swaps have occurred on the last pass. Average and worst time complexity of this algorithm is O(n²), so it is rarely used for sorting large data sets.