Bubble sort

Compare neighbors and swap only when the left number is larger, so the largest remaining number walks to the end. Equal numbers do not swap, so they keep the order they had at the start. Best case is n minus one comparisons; reversed numbers cost n times n minus one, over two.