> none of the popular sorting algorithms decide which elements to swap by looking at the whole input at each execution Yes. In particular, the O(n log n) lower

> none of the popular sorting algorithms decide which elements to swap by looking at the whole input at each execution Yes. In particular, the O(n log n) lower bound holds for comparison sorts, that is algorithms that rely on pairwise comparison only.