Sorting

Common Sorting Algorithm

Bubble Sort

In bubble sort, we start at the beginning of the array and swap the first two elements if the first is greater than the second.

Then, we go to the next pair, and so on, continously making sweeps of the array until it is sorted.

Runtime: O(n^2) average and worst case. Memory: O(1).

Selection Sort

Find the smallest element using a linear scan and move it to the front. Then find the second smallest and move it. Continue doing this until all elements are in place.

Runtime: O(n^2) average and worst case Memory: O(1)

Merge Sort

Merge sort divides the array in half, sorts each of those halves, and then merges them back together. Each of those halves has the same sorting algorithm applied to it. Eventually, you are merging just two single­ element arrays. It is the "merge" part that does all the heavy lifting.

Runtime: O(nlogn) Memory: O(n)

Quick Sort

All the real work happens in the divide step. In fact, the combine step in quicksort does absolutely nothing.In practice, quicksort outperforms merge sort, and it significantly outperforms selection sort and insertion sort.

Runtime: worst-case O(n^2), average-case O(nlogn) Memory: O(1)

Counting Sort

Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. It is not a comparison based sorting. It's running time complexity is O(n) with space proportional to the range of data.

Runtime: O(n+k) where n is the number of elements in input array and k is the range of input. Memory: O(n+k)

Comparison

Merge Sort vs Quick Sort

Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time.

Quick Sort vs Heap Sort

The most direct competitor of quicksort is heapsort. Heapsort is typically somewhat slower than quicksort, but the worst-case running time is always Θ(nlogn). Quicksort is usually faster, though there remains the chance of worst case performance except in the introsort variant, which switches to heapsort when a bad case is detected. If it is known in advance that heapsort is going to be necessary, using it directly will be faster than waiting for introsort to switch to it.