# Chunk Sort a Sequence

Your task is to input a sequence of integers and chunk sort it. You may assume the input list can always be chunked into groups of 1, 2, and 3.

# Definition

Chunk sorting (a term I made up for the purpose of this challenge) is the action of first chunking a sequence into groups of 1, 2, and 3 in a cycle and then sorting each group.

# Test cases

[1, 2, 3, 4, 5, 6, 7, 8, 9] => [[1], [2, 3], [4, 5, 6], [7], [8, 9]]
[5, 9, -2, 8, -6, 4, 5, 9, 1] => [[5], [-2, 9], [-6, 4, 8], [5], [1, 9]]
[8, 3, -1, 6, -8, 7, -1] => [[8], [-1, 3], [-8, 6, 7], [-1]]

# Scoring

The shortest code wins!

# Rules

• An invitation to look for nonstandard loopholes!
– Stef
Commented Dec 13, 2021 at 16:02

# Ruby, 49 bytes

->l{x=5;l.chunk{441[(x+=1)%12]}.map{|a,b|b.sort}}

Try it online!

Literally: chunk, then sort.

The magic number 441 is a bitmask with 1,2,3 binary digits alternatively seto to 1 or 0:

000 11 0 111 00 1

Since there are only 2 binary digits, I can't make it 3 chunks, so I make it 6 and so I use mod 12 to rotate.

# Jelly, 10 8 bytes

3Rṁx@JṢƙ

Try it online!

## How it works

3Rṁx@JṢƙ - Main link. Takes L on the left
3R       - [1,2,3]
ṁ      - Mold to length L, repeating
J   - Yield [1,2,...,len(L)]
x@    - Repeat 1 once, 2 twice, 3 thrice, 4 once, 5 twice, etc.
Ṣƙ - Sort chunks of L, grouped by the elements of [1,2,2,3,3,3,4,...]

# Husk, 6 bytes

mOC¢ḣ3

Try it online!

How?

ḣ3      # 1..3
¢        # repeated infinitely;
C         # now split the input into sublists
# of these lengths (discarding any
# extra, unused lengths);
m           # finally, for each sublist:
O          # sort it.

# 05AB1E, 10 bytes

3LI∍£€{ʒgĀ

Or alternatively (thanks to @ovs for N6%tò):

.yN6%tò}€{

Explanation:

3L          # Push list [1,2,3]
I∍        # Extend the [1,2,3] list to the same size as the input-list
£       # Split the (implicit) input-list into those parts,
# which includes trailing empty lists at the end
€{     # Sort each inner list
ʒgĀ  # Remove the empty lists:
ʒ    #  Filter the list of lists:
gĀ  #   Check if the list-length is not 0
# (after which the result is output implicitly)

.y          # Adjacent group the (implicit) input-list by:
N         #  Push the 0-based group-by index
6%       #  Modulo-6
t      #  Take the square-root of that
ò     #  Round it to the nearest integer
}€{        # After the group-by: sort each inner list
# (after which the result is output implicitly)

The N6%tò results in the sequence [0,1,1,2,2,2,0,1,1,2,2,2,...], causing the adjacent group-by to split the input-list into parts of sizes [1,2,3,1,2,3,...], which is what we want.

The first program could be 9 bytes if the input-length is guaranteed to be $$\n>1\$$:

3LI∍£€{Ô¨

See all test cases, and how it unfortunately fails for [1]. (Adding Ć after I would fix that edge-case, but unfortunately we'll then have another 10-bytes alternative.)

• I haven't found anything shorter yet, but there are a lot of interesting 12-byters using the .y ... }€{ approach, where .y} is an adjacent group-by and €{ is a sort-each. Here a test battery if anyone wants to try to find something very short for the inner portion which could be any repeating abbccc pattern based on index N. Commented Dec 10, 2021 at 19:14
• N6%tò works for another 10-byter, but I doubt this approach can be any shorter
– ovs
Commented Dec 11, 2021 at 22:19

# Jelly, 10 bytes

J%6B§=1ÄṢƙ

Try It Online!

J           [1, 2, 3, ..., len(input)]
%6         [1, 2, 3, 4, 5, 0, 1, 2, 3, ...]
B        Binary; [[1], [1, 0], [1, 1], [1, 0, 0], [1, 0, 1], [0], ...]
§       Sum each; [1, 1, 2, 1, 2, 0, ...]
=1     Equal to 1?; [1, 1, 0, 1, 0, 0, ...]
Ä    Cumulative sum; [1, 2, 2, 3, 3, 3, 4, 5, 5, 6, 6, 6, ...]
Ṣƙ  Sort chunks of the input grouped based on equal elements on the left side

# Python, 86 65 63 bytes

def f(a,i=0):
for x in a:a[i:i%3-~i]=sorted(a[i:i%3-~i]),;i+=1

Attempt This Online!

Modifies the list in-place; kinda cursed.

• I'm surprised that l[a:b:c].sort() doesn't work to sort a slice of a list in place.
– xnor
Commented Dec 11, 2021 at 13:20
• @xnor I agree, it's a bit inconsistent that slicing on the LHS is a mutable reference, but makes a copy on the RHS. Commented Dec 12, 2021 at 18:34

# Python 2, 50 bytes

f=lambda a,i=1:a and[sorted(a[:i])]+f(a[i:],i%3+1)

Try it online!

# Pip-xp, 2423 18 bytes

$AL:SN*_^@^13Ma<>6 Replit! Or, here's a 20-byte equivalent in Pip classic (with a header to simulate the -x flag): Try it online! ### Explanation$AL:SN*_^@^13Ma<>6
a     First command-line arg
<>6  Group into length-6 chunks
M      Map this function to each chunk:
^13        Split 13 into a list of digits [1;3]
_^@           Split the argument at those indices
SN*              Sort each sublist using numeric comparison
$AL: Fold the result on append-list (flattening by one level) # R, 7063 59 bytes function(a)Map(sort,split(a,rep(l<-seq(!a)-1,l%%3+1)[l+1])) Try it online! • Getting rid of ! in seq and using Map(sort,...) (from your comment) matches Dominic's 59. Commented Dec 10, 2021 at 21:15 • I think the ! needs to be there for input of length one--Dominic's solution of using [<- neatly avoids that, but I think I can still tie it. Commented Dec 10, 2021 at 21:49 • Does it actually work with input of length one now, though? Commented Dec 11, 2021 at 7:11 • Looks like it's back to the tie again. Anyway, well done! Commented Dec 11, 2021 at 9:19 # Wolfram Language (Mathematica), 53 bytes Sort/@TakeList[#,i=0;UpTo@Mod[++i,4]&/@#]/.{}->Set@$&

Try it online!

-6 bytes thanks to @alephalpha
-3 bytes thanks to @theorist
-2 bytes thanks to @att

• Tips: NestWhile can always be replaced by //.: 68 bytes Commented Dec 11, 2021 at 0:45
• –3 bytes: Sort/@TakeList[#,Take[Join@@Table[Range@3,q=Tr[1^#]],⌈q/2⌉]]& tio.run/##NcvBC4IwFMfxu3/FA6HTG2Napgdh5@gQ5W0sWDHWKBVtN/Fe4F/… Commented Dec 11, 2021 at 6:44
• 55 bytes assuming input is nonempty, 56 if we can't.
– att
Commented Dec 29, 2021 at 0:27
• actually, we can get another -2 from there
– att
Commented Dec 29, 2021 at 0:30

# JavaScript (ES6), 61 bytes

-4 and -1 thanks to Arnauld

x=>(f=n=>x+x&&[x.splice(0,++n).sort((w,z)=>w-z),...f(n%3)])$$$$

# R, 59 bytes

function(x,*=[<-)Map(sort,split(x,x*rep(seq(x),x*1:3)))

Try it online!

• Hmm, I have 60 bytes if I use the Map(sort,...) instead of lapply. I'm catching up! Commented Dec 10, 2021 at 20:38

# Retina, 24 bytes

5,6,S,
%,,2S,
%N[^,]+

Try it online! Explanation:

5,6,S,

Split the input into groups of up to six values. Limits are 0-indexed in Retina 1, so the first six values are numbered 0 to 5 and therefore the comma after the sixth value is also numbered 5, however subsequent splits are every six commas as expected, until the end of the input.

%,,2S,

Split each group into groups of 1, 2 and 3 values (if possible). The syntax ,,2 is short for ,2,2 so it only splits on the first and third comma; ,2 would be a range and so would also split on the second comma.

%N[^,]+

Sort the values in each group.

# Bash 4.4.23, 142 bytes

f()(
i=1
a=("$@") while [${#a[@]} -gt 0 ]
do
r=$r"["$(printf "%s\n" "${a[@]:0:$i}" |sort -n)"]"
a=("${a[@]:${i}}")
((i=i==3?1:i+1))
done
echo $r ) Try it here! ## Explanation i=1 > used to keep track of chunk size a=("$@")                                      > transforms the parameters as an array
while [ ${#a[@]} -gt 0 ] > while there is still some elements to "chuck sort" do r=$r[$(printf "%s\n" "${a[@]:0:$i}"|sort -n)] > construct the final result by picking only the required chunk from the array and sorts it. Store sort result in r and ad some delimiters a=("${a[@]:${i}}") > remove processed chunk from the array ((i=i==3?1:i+1)) > set size of next chunk done echo$r
• Welcome to Code Golf. Nice first answer! Commented Dec 11, 2021 at 21:57

Try it online!

# Charcoal, 48 40 bytes

≔⮌ＡθＷθ⊞υＥ⊕﹪Ｌυ³⊟θＩＥυ✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Ｌι

Try it online! Link is to verbose version of code. Explanation: Charcoal really struggles here as it has no variable length split, flatten or sort primitive (at least not on TIO).

≔⮌Ａθ

Reverse the input array.

Ｗθ

Repeat until the input array has been chunked.

⊞υＥ⊕﹪Ｌυ³⊟θ

Create a chunk of size depending on the number of chunks so far.

ＩＥυ✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Ｌι

For each chunk, get the minimum, middle and maximum elements, but skip the middle if the chunk's size is less than 3 and skip the maximum if its size is less than 2.

Previous 48-byte version didn't require the input to be completely chunkable:

ＷθＦ³«⊞υ✂θ⁰⊕κ≔✂θ⊕κＬθ¹θ»ＩＥΦυι✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Ｌι

Try it online! Link is to verbose version of code. Explanation:

Ｗθ

Repeat until the input is empty.

Ｆ³«

Take three chunks.

⊞υ✂θ⁰⊕κ

Save the chunk.

≔✂θ⊕κＬθ¹θ

Remove the chunk from the input.

»ＩＥΦυι✂⟦⌊ι⁻Σι⁺⌊ι⌈ι⌈ι⟧⁰χ⁻⁴Ｌι

For each non-empty chunk, get the minimum, middle and maximum elements, but skip the middle if the chunk's size is less than 3 and skip the maximum if its size is less than 2.

# HBL, 17 bytes

?.(1(%(0,.))('?(2,.)(+(?(<,<),
).1

Try it!

### Explanation

The first line is a recursive function that does most of the work. It takes two arguments, a list and an integer, where the integer represents the current chunk size (1, 2, or 3).

?.(1(%(0,.))('?(2,.)(+(?(<,<),
?                               If
.                              Argument 1
is truthy (non-empty):
(1                             Construct a list from
,                         Argument 2
(0  )                       Take that many elements of
.                        Arg1
(%     )                      Sorted
prepended to
('?                   Recursive call with two arguments:
(2,.)               Drop (arg2) elements of arg1
and
(+             Increment
(?            If
,         Arg2
(<  )       is less than
<        3:
,       Arg2
Else, 0
Else, empty list

Then the main function on the second line is simply:

)    Call the previous function with these arguments:
.    Argument 1 of the main function
and
1   1

# Stax, 6 bytes

£ñ+Ü5▬

Run and debug it

• first time use of |/ in an answer? Commented Dec 11, 2021 at 2:04
• I can't say I've seen it used anywhere before. Commented Dec 13, 2021 at 19:37

# C (gcc), 73 70 bytes

l;f(a,n)int*a;{for(l=0;n;n-=l,a+=l,l%=3)qsort(a,++l,4,L"\x62b078bǃ");}

Try it online!

Inputs a pointer to an array of integers and its length (because pointers in C carry no length info).
Chunk sorts the array in place.

import Data.List
f=(%)1
n%[]=[]
n%x=sort(take n x):(mod n 3+1)%drop n x

Try it Online!

-5 bytes thanks to xnor

Calling f on a list chunk sorts it.

• You can save a few bytes by defining g as an infix function: TIO
– xnor
Commented Dec 14, 2021 at 4:40
• Ah, I forgot about infix functions! Thanks for the tip, xnor! Commented Dec 14, 2021 at 18:46

# tinylisp, 194170 146 bytes

(d C(q((L P)(i L(c(map head(zip L(1to P)))(i(e P 3)(C(t(t(t L)))1)(i(e P 2)(C(t(t L))3)(C(t L)2))))(
(d S(q((L)(map merge-sort(C L 1

Try it online!

-24 thanks to DLosc suggesting implementing take instead of the hodge-podge mess of cs I was using before. -24 again by implementing take more golfily.

• @DLosc great suggestion, thanks! I'll definitely be keeping list in mind but looks like take was shorter here after all. Commented Feb 8, 2022 at 20:56
• Hm, and with the library you can do a shorter version of take: (d T(q((L N)(map head(zip L(1to N)))))), which isn't recursive so it can just be inlined: Try it online! Commented Feb 8, 2022 at 21:40

# Pari/GP, 53 bytes

a->i=0;c=2;[vecsort(a[i+1..i=j+1])|b<-a,#a>j=i+c++%3]

Try it online!

# PHP, 131 bytes

function(&$a){for($a=array_chunk($a,3),$i=-1;$a[++$i];sort($a[$i]))!$a[$i][1]|$i%3?:array_splice($a,$i,0,[[array_shift($a[\$i])]]);}

Try it online!

This is a first take, it feels awfully long, there has to be a better way.. damn these "array_" prefixes!