# How long to carry sort?

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.

### Worked example

Here we are going to apply carry sort to the list [1,2,0,3,2,1,2,4,3]

[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 so the goal is to minimize the size of your source code as measured in bytes.

## Test cases

[] -> 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

• So carry sort is a single pass through bubble sort's loop? Mar 15 at 22:22
• @Bbrk24 Bubble sort IME is not a terribly specific term, so I avoided it in the question body, but I would call this a bubble sort. Mar 15 at 22:24
• Grade up, if you have that builtin, will do a lot of the heavy lifting here.
– Neil
Mar 16 at 1:00

# R, 4140 35 bytes

Edit: -1 byte thanks to @Giuseppe and -5 bytes thanks to @Dominic van Essen.

\(x)max(order(y<-c(x,Inf))-seq(!y))


Attempt This Online!

The idea is that we look how much to the right are the elements displaced in the input versus the sorted array, and take the maximum. This is because moving elements to the right is easy and to the left is hard (moving one space to the left requires exactly one pass).

Example:

x =               1  2  0  3  2  1  2  4  3
sort(x) =         0  1  1  2  2  2  3  3  4
order(x) =        3  1  6  2  5  7  4  9  8 # positions of the input in the sorted array (sort(x) === x[order(x)])
order(x)-seq(x) = 2 -1  3 -2  0  1 -3  1 -1 # how far to the right is input vs sorted

• This is beautiful, but I think you need seq(!x) to avoid problems with single-element lists with a negative value...? Mar 16 at 11:52
• (or \(x)if(a<-sum(x|1),max(order(x)-1:a),0)...?) Mar 16 at 11:55
• @DominicvanEssen thanks, I didn't think of one-element negative inputs. Mar 16 at 12:07
• \(x)'if'(any(x),max(order(x)-seq(!x)),0) for 40 bytes. If the list is empty or contains all zeros (falsey), it's already sorted. Mar 16 at 13:30
• Mar 16 at 15:32

# JavaScript (ES6), 50 bytes

This is inspired by @pajonk's excellent answer. But instead of explicitly sorting the input array, we subtract from the position of each element the number of elements that are less than or equal to it.

a=>a.map(m=(v,i)=>a.map(V=>i-=V<=v)|m>++i?0:m=i)|m


Try it online!

### Commented

a =>         // a[] = input array
a.map(m =    // initialize m to a non-numeric value
(v, i) =>    // for each value v at position i in a[]:
a.map(V => //   for each value V in a[]:
i -=     //     decrement i if
V <= v //     V is less than or equal to v
) |        //   end of inner map()
m > ++i ?  //   increment i; if m is greater than i:
0        //     do nothing
:          //   else:
m = i    //     update m to i
) | m        // end of outer map(); return m


# JavaScript (ES6), 66 bytes

-1 if we return false for 0.

f=A=>([m,...a]=[...A,,],a=a.map(v=>v<m?v:m+![m=v]))==A+''?0:1+f(a)


Try it online!

### Commented

f = A =>           // recursive function taking the input array A[]
(                  // split into:
[ m,             //   m   = first element
...a ] =    //   a[] = all remaining elements
// the array defined as:
[ ...A,, ],      //   A[] padded with a trailing undefined value
a = a.map(v =>   // for each element v in a[]:
v < m ?        //   if v is less than m:
v            //     leave v unchanged
:              //   else:
m + ![m = v] //     put m here and update m to v
)                // end of map(); save the result in a[]
) == A + '' ?      // if a[] is equal to A[]:
0                //   stop
:                  // else:
1 +              //   increment the final result and do
f(a)             //   a recursive call with the updated array


# Charcoal, 5333 31 bytes

≔⟦⟧ηＷ⁻θυ«⊞υ⌊ιＦ⌕Ａθ⌊ι⊞η⁻κＬη»Ｉ∨⌈η⁰


Try it online! Link is to verbose version of code. Explanation: Having written my comment, I finally got around to implementing a version using grade up.

≔⟦⟧η


Ｗ⁻θυ«


Repeat until the list has been graded.

⊞υ⌊ι


Ｆ⌕Ａθ⌊ι⊞η⁻κＬη


Save the offsets of each matching element in the list.

»Ｉ∨⌈η⁰


Output the maximum, or 0 if the list was empty.

# Excel (ms365), 137 bytes

Within the windows version one can create their own named function using the named manager. Here we will create a function named 'Z':

=LAMBDA(a,b,IF(AND(a=SORT(a)),b,Z(DROP(REDUCE({0;0},a,LAMBDA(c,d,LET(y,TAKE(c,-1),IF(d>y,VSTACK(c,d),VSTACK(DROP(c,-1),d,y))))),2),b+1)))


Now you can call 'Z' using:

=Z(<YourVerticalRange>,0)


For example: If one would like to try this online, I tried to mimic this using Google Sheets:

=LAMBDA(a,b,IF(INDEX(AND(a=SORT(a))),b,Z(QUERY(REDUCE({0;0},a,LAMBDA(c,d,LET(y,INDEX(c,COUNT(c)),IF(d>y,VSTACK(c,d),VSTACK(QUERY(c,"limit "&COUNT(c)-1),d,y))))),"offset 2"),b+1)))(a,b) # Vyxal, 25 bytes

{:ÞṠ¬|÷^!(~<ß$‟)„$‟^W&›}¥


Try it Online!

Count how many times the sweep is applied until it's sorted.

• Get outgolfed lol :p Mar 16 at 11:50
• @TheThonnu you say that like it's something that doesn't happen on days that end in y :p Mar 16 at 12:11

# 05AB1E, 19 15 bytes

ΔZªćUεDX›iXsU]N


-4 bytes porting @Arnauld's JavaScript answer, so make sure to upvote him as well!

Δā<ü2vDyè©›i®yRǝ]N


Explanation:

Δ                   # Loop until the result no longer changes (aka, until it's sorted),
# using the (implicit) input-list
Z                  #  Push the maximum of the list (without popping)
ª                 #  Append this maximum to the list
ć                #  Extract head; pop and push remainder-list and first item
#  separately to the stack
U               #  Pop and store this first item in variable X
ε              #  Map over the remainder-list:
D             #   Duplicate the current integer
X›i          #   Pop the copy, and if it's larger than X:
X         #    Push X
sU        #    Swap, pop, and store the current integer as new X
#   (implicit else: keep the current integer, hence the need for the
#   Duplicate before the if-statement)
]                   # Close the if-statement; map; and changes-loop
N                  # Push the final (0-based) index of the changes-loop
# (which is output implicitly as result)

Δ                ]N # Same as above:
ā                  #  Push a list in the range [1,length] (without popping)
<                 #  Decrease it to 0-based range [0,length)
ü2               #  Get all overlapping pairs of this index-list
v              #  Pop and loop over each index-pair y:
Dyè           #   Get the values at indices y in a copy of the current list
©          #   Store this pair of values in variable ® (without popping)
›i       #   Pop the pair, and if the first is larger than the second:
®yRǝ   #    Swap the values at the index-pair y within the list:
®      #     Push values-pair ®
yR    #     Push the reversed of index-pair y
ǝ   #     Insert the values at those reversed indices to the list

• Wouldn't ZªćU solve the potential problem with ćUZª?
– Neil
Mar 16 at 9:53
• @Neil You're completely right indeed, thanks. Can't believe I've overlooked that.. Mar 16 at 9:57

# R, 90 82 bytes

Edit: -8 bytes thanks to Giuseppe

f=\(l)if(is.unsorted(l),{l[c(F,d,T)]=l[c(T,d<-diff(cummax(l))>0)];f(l[-1])+1},0)


Attempt This Online!

Recursively performs carry-sort and counts how many times it's needed until the argument is sorted.

Take a look at pajonk's much more elegant and shorter approach that simply calculates the right answer directly, though...

# Python + numpy, 67 65 bytes

Edit: -2 bytes thanks to @ovs.

lambda x:len(x)and max(argsort(x)-r_[:len(x)])
from numpy import*


Attempt This Online!

• Making some more use of numpy, range(len(x)) can be r_[:len(x)]
– ovs
Mar 18 at 16:56

# Ruby, 47 ... 41 bytes

->l{l.map{*l,c=l;l.count{|a|a>c}}.max||0}


Try it online!

• Something is off here, the third case on your TIO link produces the wrong output. And you need to count the f= as this is recursive.
– ovs
Mar 17 at 11:17
• @ovs Is fixed now
– G B
Mar 31 at 14:36

# BQN, 7 bytesSBCS

Another port of pajonks R answer.

0⌈´⍋-⊒˜


Run online!

# VyxalG, 9 7 6 bytes

⇧$ẏ-0J  Port of @pajonk's R answer -2 thanks to @Neil #### Explanation ⇧$ẏ-0J  # Implicit input
⇧       # Grade up: push the indices which will sort the list
$ẏ # Swap and push a list in the range [0, len(input)) - # Subtract the range from the grade up list 0J # Append a 0 to this list # G flag gets the maximum # Implicit output  Old: [⇧›$ż-G|0  # Implicit input
[          # If it isn't empty:
⇧         #  Grade up: push the indices which will sort the list
›        #  Increment it to make it one-indexed
$ż # Swap and push a list in the range [1, len(input)] - # Subtract the range from the grade up list G # Pop and push the maximum item |0 # Otherwise, push 0 # Implicit output  • I think ⇧$ẏ-0JG saves 2 bytes.
– Neil
Mar 16 at 14:40
• @Neil thanks. We can use the G flag as well to save another one. Mar 16 at 14:46

# Jelly, 4 bytes

Ụ_JṀ


A monadic Link that accepts the list and yields the number of required passes.

Try it online!

### How?

Just as pajonk's R answer, but with automatic 0 as the maximum of an empty list.

Ụ_JṀ - Link: List, A
Ụ    - grade-up (A) -> list of 1-indexed indices of the sorted values
J  - range of length (A) -> 1-based indices = [1..length(A)]
_   - (graded indices) subtract (indices)
Ṁ - maximum (the maximum of an empty list is 0)


# J, 14 bytes

[:>./0,/:-i.@#


Try it online!

## Explanation

Same approach as a few answers.

[:>./0,/:-i.@#
-       and subtract from each position
i.@#   the corresponding element in the range [0, size)
0,          prepend zero (edge case of empty lists)
[:               and then
>./            take the maximum of that array (which is otherwise -∞ for empty lists)


# Factor, 46 bytes

[ arg-sort [ - ] map-index 0 suffix supremum ]


Try it online!

• arg-sort Get the indices that would sort the sequence. (aka grade up/inverse permutation)
• [ - ] map-index Subtract each index from its element.
• 0 suffix Append a 0.
• supremum Get the maximum element.

# Desmos, 52 48 bytes

s=[0...x.length]
f(x)=max(sort(s,join(0/0,x))-s)


Try it on Desmos!

One of the only times where 0/0 is useful. Based on pajonk's answer.
-4 bytes thanks to Aiden Chow.

• This seems to work for 48 bytes. Mar 21 at 4:53

# APL(Dyalog Unicode), 9 bytes SBCS

⌈/0,⍋-⍳∘≢


Try it on APLgolf!

### Explanation

⌈/0,⍋-⍳∘≢
≢       ⍝ length of the input
⍳∘        ⍝ create a range from 1 to the length
-         ⍝ subtract that list from...
⍋          ⍝ the input graded up
0,            ⍝ prepend a zero
⌈/              ⍝ get the maximum of the resulting list


Just for reference, this is what the train tree looks like:

  ┌─┴─┐
/ ┌─┼───┐
┌─┘ 0 , ┌─┼─┐
⌈       ⍋ - ∘
┌┴┐
⍳ ≢


# Wolfram Language (Mathematica), 66 bytes

Golfed version, try it online!

x~Append~∞//Ordering//Max[#-Range@*Length@#/.Thread[Not@#->1]]&;


Ungolfed version

f[x_List] := Module[{y, yOrder, seqY},
y = Append[x, Infinity];
yOrder = Ordering[y];
seqY = Range[Length[yOrder]] /. Thread[Not[yOrder] -> 1];
Max[yOrder - seqY]
]

(* function testing *)
f[{}]//Print (* -> 0 *)
f[{-10}]//Print  (* -> 0 *)
f[{-2, 3, 9}]//Print  (* -> 0 *)
f[{4, 1, 2, 3}]//Print  (* -> 1 *)
f[{1, 3, 2, 4}]//Print  (* -> 1 *)
f[{4, 3, 2, 1}]//Print  (* -> 3 *)
f[{0, -1, -2, -3, -4}]//Print  (* -> 4 *)
f[{1, 2, 0, 3, 2, 1, 2, 4, 3}]//Print  (* -> 3 *)
f[{1, 1, 2, 2, 3, 3, 4, 4}]//Print  (* -> 0 *)
f[{4, 4, 3, 3, 2, 2, 1, 1}]//Print  (* -> 6 *)