there are some very basic sorts: selection sort, insertion sort, bubble sort, merge sort, quick sort and bulit_in sort.we do have some touch down during CSC108, we learned three O(n^2) algorithms: bubble sort, insertion sort and selection sort. then in CSC148, there are more effencient way of sortinbg quicksort(O(n log n)), merge sort(O(n log n)), count sort(O(n) but it has preconditions), Tim sort(O(n log n), used in Python built-in sorting method)
there is a cheat chart for helping remember
| Big-Oh | Mergesort | Quicksort | Insertionsort | Selectionsort | Bubblesort | |
| BestCase | O(nlgn) | O(nlgn) | O(n) | O(n^2) | O(n^2) | |
| AverageCase | O(nlgn) | O(nlgn) | O(n^2) | O(n^2) | O(n^2) | |
| WorstCase | O(nlgn) | O(n^2) | O(n^2) | O(n^2) | O(n^2) |
