- Time Complexity: O(n^2)
- Space Complexity: O(1)
Similar to Bubble Sort, but:
- does only 1 pass through the array
- places items in the right spots directly instead of moving them 1 field at a time
It’s slow, but it comes useful when:
the dataset is almost sorted
we’re sorting a stream of incoming data
Time Complexity: O(n^2)
Space Complexity: O(1)
It uses the divide-and-conquer approach. We split the array to single-element arrays and then join them together, sorting in the process.
- Time Complexity: O(n log(n))
- Space Complexity: O(n)
It’s a recursive algorithm where we select pivot point and move elements around the pivot in a way that elements less than pivot are on the right, and elements that are greater are on the right. Then, we do the same in the two partitions that the pivot created.
It’s a divide-and-conquer technique.
There are different strategies when it comes to selecting the pivot point. It could be:
- first element
- last element
- random element
- something else
- Time Complexity: O(n log n) (worst case: O(n^2) - when the picked pivot is the smallest or the greatest element)
- Space Complexity: O(log n)