===== ISTEM =====
Write a Python function that sorts a list of integers that are all between 0 and 1000, with a guaranteed O(n) worst-case running time for large n. Briefly explain why it meets that bound.

===== HAM YANIT =====
To sort a list of integers between 0 and 1000 with a guaranteed **O(n)** worst-case running time, we can use **Counting Sort**. This algorithm is efficient for sorting integers within a known, limited range.

### ✅ Python Function: Counting Sort

```python
def counting_sort(arr):
    # Find the range of the input
    max_val = max(arr)
    min_val = min(arr)
    
    # Initialize the count array
    count = [0] * (max_val - min_val + 1)
    
    # Count occurrences
    for num in arr:
        count[num - min_val] += 1
    
    # Reconstruct the sorted array
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i + min_val] * count[i])
    
    return sorted_arr
```

### ✅ Explanation:

- **Time Complexity**: `O(n + k)`, where `n` is the number of elements and `k` is the range of the input values.
  - Since the input values are **guaranteed to be between 0 and 1000**, the range `k = 1001` is a **constant**.
  - Therefore, the time complexity becomes **O(n)**, which is optimal for large `n`.

- **Space Complexity**: `O(k)` → `O(1)` in this case, since `k` is a constant.

### ✅ Why it meets the O(n) worst-case bound:

- Counting Sort is a **non-comparison-based** sort.
- It uses the fact that the input values are **bounded** (between 0 and 1000), which allows it to sort in linear time.
- The algorithm avoids the O(n log n) lower bound for comparison-based sorts by directly counting occurrences of each value and reconstructing the sorted list.

This makes **Counting Sort** an ideal choice for this problem.