Algorithms and Data Structures · Senior · Question 63 of 75
What is the complexity of Array.prototype.sort in V8 on an array that's already sorted?
- ✓Correct answer: About O(n)
- 2O(n log n) with no shortcut
- 3O(n²)
Explanation
Timsort detects that the whole array is one ascending run and only does a linear check. This is one reason to prefer the built-in sort over a handwritten quicksort.