Not only in best case. Haven't seen this elsewhere, and know only few people who know that, so, a kind of a puzzle: what are the conditions when bubblesort is always O(n)?