Sorting Algorithm Speed Round
Quick drills on quicksort, mergesort, heapsort, and counting sort: best / average / worst times, stability, and when each one wins.
Question Bank
Easy
JavaScript
3 questions
sorting
merge-sort
quiz
fundamentals
280 views
8
Match each sort to its average-case time and worst-case time: quicksort, mergesort, heapsort, counting sort (on n integers in range [0, k]).
Which of these sorts are stable by default: quicksort, mergesort, heapsort, insertion sort? Define stability in one sentence.
Implement counting sort for an integer array where every value is in [0, k]. Return the sorted array.
Examples
Example 1:
Input: arr = [3, 1, 4, 1, 5, 2, 0], k = 5
Output: [0, 1, 1, 2, 3, 4, 5]
Explanation: Count occurrences into a size-(k + 1) bucket array, then emit values in order with the right multiplicities. O(n + k) time, O(n + k) space. Beats the O(n log n) comparison lower bound when k is small relative to n.function countingSort(arr, k) {
// TODO
}