Carry sort is an \$O(n)\$ "sorting" algorithm. Here's how it works. The algorithm moves left to right along a list. As it traverses a list it "carries" a single item, the largest item it has encountered so far. Once it encounters a larger item it picks up that item and drops the item it is already carrying in place. When it gets to the end it drops the item that it is carrying (the largest item in the list) at the end of the list.
Here we are going to apply carry sort to the list
[1,2,0,3,2,1,2,4,3] ^ [ 2,0,3,2,1,2,4,3] ^ 1 [ 1,0,3,2,1,2,4,3] ^ 2 [ 1,0,3,2,1,2,4,3] ^ 2 [ 1,0,2,2,1,2,4,3] ^ 3 [ 1,0,2,2,1,2,4,3] ^ 3 [ 1,0,2,2,1,2,4,3] ^ 3 [ 1,0,2,2,1,2,4,3] ^ 3 [ 1,0,2,2,1,2,3,3] ^ 4 [ 1,0,2,2,1,2,3,3] ^ 4 [ 1,0,2,2,1,2,3,3,4] ^
Here we can see that carry sort has definitely made the list more sorted than it was, but it's not perfectly sorted.
If you repeatedly apply carry sort to a list it will eventually sort the list. Your task is to take a list of integers and determine the minimum number of passes required for carry sort to sort the input list in ascending order.
This is code-golf so the goal is to minimize the size of your source code as measured in bytes.
 -> 0 [-2,3,9] -> 0 [4,1,2,3] -> 1 [1,3,2,4] -> 1 [4,3,2,1] -> 3 [0,-1,-2,-3,-4] -> 4 [1,2,0,3,2,1,2,4,3] -> 3