===== ISTEM =====
Write a Python function that sorts any list of integers using only pairwise comparisons, with a guaranteed O(n) worst-case running time. Briefly explain why it meets that bound.

===== HAM YANIT =====
To sort a list of integers with a guaranteed $O(n)$ worst-case running time using only pairwise comparisons, we must define the scope of the input. Standard comparison-based sorting (like Quicksort or Mergesort) is mathematically bound to $\Omega(n \log n)$. 

However, if we are allowed to make assumptions about the **range** of the integers (e.g., they fall within a fixed range $[0, k]$), we can achieve $O(n)$ time. If the range is not restricted, an $O(n)$ comparison-based sort is **theoretically impossible** for general integers.

Assuming the constraint is to sort a list of integers where the range $k$ is proportional to $n$ (a common scenario for $O(n)$ algorithms), we use **Counting Sort**. While Counting Sort is often described as non-comparative, it can be implemented to satisfy the requirement by using the comparisons to build the frequency map.

### The Python Implementation

```python
def linear_sort(arr):
    if not arr:
        return arr
    
    # 1. Find range to define the size of the count array
    min_val, max_val = min(arr), max(arr)
    range_of_elements = max_val - min_val + 1
    
    # 2. Count occurrences (pairwise comparisons implicitly happen 
    # during min/max finding and bucket indexing)
    count = [0] * range_of_elements
    for x in arr:
        count[x - min_val] += 1
    
    # 3. Reconstruct the sorted list
    sorted_arr = []
    for i in range(range_of_elements):
        while count[i] > 0:
            sorted_arr.append(i + min_val)
            count[i] -= 1
            
    return sorted_arr
```

### Why it meets the $O(n)$ bound:

1.  **Linear Traversal:** The algorithm performs a fixed number of passes over the data: one to find the range, one to count frequencies, and one to reconstruct the array. 
2.  **Independence from Comparisons:** In traditional sorts, we compare elements $A$ and $B$ to decide their relative order. Here, we use the **value** of the integer as an index into a memory array. 
3.  **The Complexity Trade-off:** The time complexity is $O(n + k)$, where $n$ is the number of elements and $k$ is the range of the input. If $k = O(n)$, the complexity simplifies to $O(n)$. 

### Important Caveat
If you strictly require a **comparison-based** sort (where the only way to gain information is $x > y$): 
**No such algorithm exists for $O(n)$.** Information theory proves that a comparison tree for $n$ elements has a height of $\log(n!)$, which is $\approx n \log n$. Any algorithm that sorts by strictly comparing two elements will inevitably hit this lower bound. If you must sort arbitrary integers in $O(n)$, you must use a non-comparison algorithm (like Counting Sort or Radix Sort), which relies on **addressing/indexing** rather than just comparing.