# Why does sort! allocate inside loops when the input is large?
**URL:** https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255
**Category:** General Usage
**Created:** [October 18, 2025, 3:20am UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255 "2025-10-18T03:20:55Z")
**Posts on this page:** 7
**Page:** 1
### Author:  [@HMegh](https://discourse.julialang.org/u/HMegh)
#### Post date: [October 18, 2025, 3:20am UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255/1 "2025-10-18T03:20:55Z")
Hi,
I have noticed that `sort!` allocates when called repetitively, but I am not sure why since I did not expect it to allocate:
```julia-auto
v=rand(1000);
@btime sort!(v)
# 1.744 μs (0 allocations: 0 bytes)
```
In my code, I need to analyze columns of a large matrix of data. Typically, it is better to sort each column first before doing anything (like calculating quantiles, medians,…). Here’s a MWE
```julia-auto
function quant(U)
d,n=size(U)
v=zeros(d)
quants=zeros(n)
for j=1:n
copy!(v,view(U,:,j))
sort!(v)
quants[j]=quantile!(v,.2;sorted=true)
end
return quants
end
```
However, this function allocates and it is seems that the culprit is the `sort!(v)` line (without it, there are only 5-6 allocations).
```julia-auto
U=rand(1000,1000)
@btime quant($U)
# 20.244 ms (6006 allocations: 9.82 MiB)
```
Curiously enough, when `size(U,1)` is small, there are no allocations
```julia-auto
U=rand(10,1000);
@btime quant($U)
# 160.864 μs (5 allocations: 8.02 KiB)
```
Any ideas on why this is happening?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [October 18, 2025, 3:40am UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255/2 "2025-10-18T03:40:55Z")
TLDR is that Julia uses an algorithm called Scratch quick sort that uses an allocation in order to be both faster than regular quicksort and stable. See [https://www.youtube.com/watch?v=RIhCBTx5TYA](https://www.youtube.com/watch?v=RIhCBTx5TYA) for details (this also might be a case where we use Radix sort which also allocates). We have an API for passing in a scratch buffer to `sort` but I’m not sure if that is part of the public interface. @Lilith can you confirm?
---
### Author:  [@Oscar\_Smith](https://discourse.julialang.org/u/Oscar_Smith)
#### Post date: [October 18, 2025, 3:48am UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255/3 "2025-10-18T03:48:35Z")
Specifically, defining:
```julia-auto
function quant(U)
d,n=size(U)
v=zeros(d)
quants=zeros(n)
scratch = similar(quants)
for j=1:n
copy!(v,view(U,:,j))
sort!(v; scratch)
quants[j]=quantile!(v,.2;sorted=true)
end
return quants
end
```
deletes half of the allocations and is 25% faster. (the other half come from a line in Radix sort that has the comment `# TODO use scratch for this`
---
### Author:  [@HMegh](https://discourse.julialang.org/u/HMegh)
#### Post date: [October 19, 2025, 1:10am UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255/4 "2025-10-19T01:10:54Z")
Thanks for sharing. I notice that Julia is not using ScratchQuickSort by default (at least for the example `U=rand(1000,1000)`), but when when I specify the algorithm, the allocations disappear. I will include some benchmarks below in case someone stumbles upon this thread in the future.
```julia-auto
function quant(U,alg)
d,n=size(U)
v=zeros(d)
quants=zeros(n)
scratch=zeros(d)
for j=1:n
copy!(v,view(U,:,j))
sort!(v;alg=alg,scratch=scratch)
quants[j]=quantile!(v,.2;sorted=true)
end
return quants
end
U=rand(1000,1000);
@btime quant($U,$(Base.Sort.ScratchQuickSort()));
# 42.819 ms (9 allocations: 23.65 KiB)
```
This is faster than the regular QuickSort
```julia-auto
@btime quant($U,$(QuickSort))
# 55.677 ms (9 allocations: 23.65 KiB)
```
But it is slower than the `DefaultStable` algorithm (which alllocates)
```julia-auto
@btime quant($U,$(Base.Sort.DefaultStable()));
# 16.796 ms (3009 allocations: 2.14 MiB)
```
As far as I can tell, there is a trade-off between allocations and speed,
---
### Author:  [@Lilith](https://discourse.julialang.org/u/Lilith)
#### Post date: [October 21, 2025, 5:17pm UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255/5 "2025-10-21T17:17:18Z")
Yep, this is all correct. And no `scratch` is not part of the public interface, largely because the appropriate eltype for the scratch array is non-obvious.
---
### Author:  [@DNF](https://discourse.julialang.org/u/DNF)
#### Post date: [October 21, 2025, 9:31pm UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255/6 "2025-10-21T21:31:56Z")
> [@HMegh](#):
>
> Typically, it is better to sort each column first before doing anything (like calculating quantiles, medians,…). Here’s a MWE
In this particular case it is better to _not_ sort first, and just leave it to the `quantile!` function (which can make do with a partial sort.) This might be different in a more realistic scenario, perhaps.
---
### Author:  [@DNF](https://discourse.julialang.org/u/DNF)
#### Post date: [October 21, 2025, 9:46pm UTC](https://discourse.julialang.org/t/why-does-sort-allocate-inside-loops-when-the-input-is-large/133255/7 "2025-10-21T21:46:06Z")
I couldn’t find any sorting functions that do `sort!(output, input)`. That would be a good solution in many cases, I think, and would allow you to do
```julia-auto
sort!(output, view(U, :, j))
```
or similar with `partialsort!`