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.