- The best we can do for a comparison-based sorting algorithm is
. -
The intuition is as follows: We can frame sorting as a search operation applied on a list of permutations on a decision Tree where internal nodes correspond to comparison and swap operations. There are
permutations for a list of elements and the best we can do is binary search which will take time. Stirling’s approximation then gives that
.
-
Bubble Sort
- Compare the current element with the one after it. Swap their values if needed. Sorting stops when no more swaps can be performed.
- The larger elements bubble to the top of the list.
- Worst case:
- Best Case:
- Average Case:
- Space Complexity:
auxiliary.
Insertion Sort
- Remove one element from the input data, find where it goes in the sorted array and insert it there.
- Generally performs better than Bubble and Selection Sort.
- Worst Case:
- Best Case:
- Average Case:
- Space Complexity:
auxiliary
Selection Sort
- Divide the input into two parts — a sorted sublist to be built up from one side (the left) of the list and an unsorted sublist consisting of the rest of the list.
- Proceed by finding the smallest (or largest) element in the unsorted sublist and exchanging it with the leftmost unsorted element. In effect, the boundary between sorted and unsorted sublists moves left to right.
- Worst Case:
- Best Case:
- Average Case:
- Space Complexity:
auxiliary
Merge Sort
- A divide and conquer algorithm that works as follows.
- Recursively divide the unsorted list into
sublists. - Sort each sublist.
- Repeatedly merge sublists to produce new sorted sublists until only one sublist is left. This is the sorted list
- Recursively divide the unsorted list into
- Worst Case:
- Best Case:
typical, - Average Case:
- Space Complexity:
auxiliary memory (using an array)
Quick Sort
-
A divide and conquer algorithm that proceeds as follows:
- Select a pivot element from the array. Partition the other elements into two sub-arrays. On the left of the pivot are those less than the pivot. On the right of the pivot are those greater than the pivot.
- Sort the subarrays (either using another round of quick sort or simple sorting).
-
Worst Case:
-
Best Case:
-
Average Case:
-
Space Complexity:
auxiliary memory (using an array)
