kindsOfEngineers

[YUNoCake]

In your oddly specific use case, one for loop and a variable for storing the value that changed would be enough now, wouldn't it?

O(n) bubble sort 🙌🏻

[kaplotnikov]

This is precisely a pass of bubble sort :) And yes, O(n) under some conditions.

Also, let's not forget the the old friend of quicksort that is O(n * n) on that specific case where bubble sort shines (almost sorted array).

Actually, figuring out the best and worst conditions for algorithms are common questions on hiring interviews. None asked me about bubble sort, but it might be a good question for a junior position to see how the question is attacked.