| Algorithm | Description | Run Time |
|---|---|---|
| Mergesort | ||
| Quicksort | There are may versions of Quicksort, which is one of the most popular sorting methods due to its speed | Best: O(N lg N), Avg: O(N lg N), Worst:O(N^2) |
| Heapsort | Add all items into a heap. Pop the largest item from the heap and insert it at the end (final position). Repeat for all items. | Best/Avg/Worst: O(N lg N) |
| Bubble Sort | Starting on the left, compare adjacent items and keep “bubbling” the larger one to the right (it’s in its final place). Bubble sort the remaining N -1 items. | Best: O(n), Worst:O(N^2) |
| Insertion Sort | Start with a sorted list of 1 element on the left, and N-1 unsorted items on the right. Take the first unsorted item (element #2) and insert it into the sorted list, moving elements as necessary. We now have a sorted list of size 2, and N -2 unsorted elements. Repeat for all elements. | Best: O(N), Worst:O(N^2) |
| Selection Sort | Scan all items and find the smallest. Swap it into position as the first item. Repeat the selection sort on the remaining N-1 items. | Best/Worst: O(N^2) |
| Counting Sort | Assuming the data are integers, in a range of 0-k. Create an array of size K to keep track of how many items appear (3 items with value 0, 4 items with value 1, etc). Given this count, you can tell the position of an item — all the 1’s must come after the 0’s, of which there are 3. Therefore, the 1’s start at item #4. Thus, we can scan the items and insert them into their proper position. | Best/Avg/Worst: O(N) |
| Radix Sort | Get a series of numbers, and sort them one digit at a time (moving all the 1000’s ahead of the 2000’s, etc.). Repeat the sorting on each set of digits. | Best/Avg/Worst: O(N) |