Hi all,

how do I sort by multiple columns?

Example:
+++
Borgentreich;D9386;Lindenstätte;1;;32;520150.696;5709236.354
Borgentreich;D9444;Auf der Lindenstätte;1;;32;519950.850;5708982.109
Borgentreich;D9444;Auf der Lindenstätte;2;;32;519926.937;5708966.116
Borgentreich;D9444;Auf der Lindenstätte;3;;32;520008.619;5709083.464
Borgentreich;D9444;Auf der Lindenstätte;4;;32;519860.278;5709041.468
Borgentreich;T2960;Lindenstätte;12;;32;519622.835;5709023.590
Borgentreich;T2960;Lindenstätte;6;;32;519696.745;5709038.833
Borgentreich;T2960;Lindenstätte;4;;32;519722.956;5709043.915
Borgentreich;T2960;Lindenstätte;15;;32;519489.638;5709077.693
Borgentreich;T2960;Lindenstätte;24;;32;519518.763;5709090.026
Borgentreich;T2960;Lindenstätte;18;;32;519559.108;5709037.356
Borgentreich;T2960;Lindenstätte;14;;32;519596.623;5709013.684
Borgentreich;T2960;Lindenstätte;16;;32;519569.141;5709017.854
Borgentreich;T2960;Lindenstätte;22;;32;519540.257;5709072.032
Borgentreich;T2960;Lindenstätte;26;;32;519503.270;5709103.321
Borgentreich;T2960;Lindenstätte;2;;32;519758.267;5709057.635
Borgentreich;T2960;Lindenstätte;10;;32;519648.417;5709028.865
Borgentreich;T2960;Lindenstätte;11;;32;519607.438;5708989.545
Borgentreich;T2960;Lindenstätte;3;;32;519732.686;5709020.833
Borgentreich;T2960;Lindenstätte;7;;32;519678.983;5709007.380
Borgentreich;T2960;Lindenstätte;9;;32;519651.859;5709000.462
Borgentreich;T2960;Lindenstätte;5;;32;519708.841;5709015.137
Borgentreich;T2960;Lindenstätte;1;;32;519778.725;5709026.584
Borgentreich;T2960;Lindenstätte;8;;32;519673.036;5709040.372
+++

I want to sort
* first by column 4, numerical,
* second by column 2
* third by column 3

So the result should be
+++
Borgentreich;D9444;Auf der Lindenstätte;1;;32;519950.850;5708982.109
Borgentreich;D9444;Auf der Lindenstätte;2;;32;519926.937;5708966.116
Borgentreich;D9444;Auf der Lindenstätte;3;;32;520008.619;5709083.464
Borgentreich;D9444;Auf der Lindenstätte;4;;32;519860.278;5709041.468
Borgentreich;D9386;Lindenstätte;1;;32;520150.696;5709236.354
Borgentreich;T2960;Lindenstätte;1;;32;519778.725;5709026.584
Borgentreich;T2960;Lindenstätte;2;;32;519758.267;5709057.635
Borgentreich;T2960;Lindenstätte;3;;32;519732.686;5709020.833
Borgentreich;T2960;Lindenstätte;4;;32;519722.956;5709043.915
Borgentreich;T2960;Lindenstätte;5;;32;519708.841;5709015.137
Borgentreich;T2960;Lindenstätte;6;;32;519696.745;5709038.833
Borgentreich;T2960;Lindenstätte;7;;32;519678.983;5709007.380
Borgentreich;T2960;Lindenstätte;8;;32;519673.036;5709040.372
Borgentreich;T2960;Lindenstätte;9;;32;519651.859;5709000.462
Borgentreich;T2960;Lindenstätte;10;;32;519648.417;5709028.865
Borgentreich;T2960;Lindenstätte;11;;32;519607.438;5708989.545
Borgentreich;T2960;Lindenstätte;12;;32;519622.835;5709023.590
Borgentreich;T2960;Lindenstätte;14;;32;519596.623;5709013.684
Borgentreich;T2960;Lindenstätte;15;;32;519489.638;5709077.693
Borgentreich;T2960;Lindenstätte;16;;32;519569.141;5709017.854
Borgentreich;T2960;Lindenstätte;18;;32;519559.108;5709037.356
Borgentreich;T2960;Lindenstätte;22;;32;519540.257;5709072.032
Borgentreich;T2960;Lindenstätte;24;;32;519518.763;5709090.026
Borgentreich;T2960;Lindenstätte;26;;32;519503.270;5709103.321
+++

I tried both
sort -k4 -t";" -n | sort -k2,2 -t";" | sort -k3,3 -t";"
and
sort -k4 -t";" -n -k2,2 -k3,3
and some permutations and reverted orders, without success.
The sort by column 4 just gets lost or resorted.

I'm not sure about the man page
-k, --key=POS1[,POS2]
start a key at POS1, end it at POS2 (origin 1)

So I tried relative positions with
-k3,1
as well, without success.

How do I apply the sort syntax properly?

Thanks
Martin

On Wed, 19 Apr 2023 09:27:12 +0200
Martin Trautmann <t-usenet@gmx.net> wrote:
>
> Hi all,
>
> how do I sort by multiple columns?
>
> Example:
> +++
> Borgentreich;D9386;Lindenstätte;1;;32;520150.696;5709236.354
> Borgentreich;D9444;Auf der Lindenstätte;1;;32;519950.850;5708982.109
> Borgentreich;D9444;Auf der Lindenstätte;2;;32;519926.937;5708966.116
> Borgentreich;D9444;Auf der Lindenstätte;3;;32;520008.619;5709083.464
> Borgentreich;D9444;Auf der Lindenstätte;4;;32;519860.278;5709041.468
> Borgentreich;T2960;Lindenstätte;12;;32;519622.835;5709023.590
> Borgentreich;T2960;Lindenstätte;6;;32;519696.745;5709038.833
> Borgentreich;T2960;Lindenstätte;4;;32;519722.956;5709043.915
> Borgentreich;T2960;Lindenstätte;15;;32;519489.638;5709077.693
> Borgentreich;T2960;Lindenstätte;24;;32;519518.763;5709090.026
> Borgentreich;T2960;Lindenstätte;18;;32;519559.108;5709037.356
> Borgentreich;T2960;Lindenstätte;14;;32;519596.623;5709013.684
> Borgentreich;T2960;Lindenstätte;16;;32;519569.141;5709017.854
> Borgentreich;T2960;Lindenstätte;22;;32;519540.257;5709072.032
> Borgentreich;T2960;Lindenstätte;26;;32;519503.270;5709103.321
> Borgentreich;T2960;Lindenstätte;2;;32;519758.267;5709057.635
> Borgentreich;T2960;Lindenstätte;10;;32;519648.417;5709028.865
> Borgentreich;T2960;Lindenstätte;11;;32;519607.438;5708989.545
> Borgentreich;T2960;Lindenstätte;3;;32;519732.686;5709020.833
> Borgentreich;T2960;Lindenstätte;7;;32;519678.983;5709007.380
> Borgentreich;T2960;Lindenstätte;9;;32;519651.859;5709000.462
> Borgentreich;T2960;Lindenstätte;5;;32;519708.841;5709015.137
> Borgentreich;T2960;Lindenstätte;1;;32;519778.725;5709026.584
> Borgentreich;T2960;Lindenstätte;8;;32;519673.036;5709040.372
> +++
>
> I want to sort
> * first by column 4, numerical,
> * second by column 2
> * third by column 3
>
> So the result should be
> +++
> Borgentreich;D9444;Auf der Lindenstätte;1;;32;519950.850;5708982.109
[...]
> Borgentreich;D9386;Lindenstätte;1;;32;520150.696;5709236.354

Why are these 2 lines sorted this way ? Column 4 is the same ("1" in
both) so it boils down to how "D9444" and "D9386" get sorted. What
comes first and why ? It seems to me that "D9386" comes earlier than
"D9444" .

Your locale may also turn out to be relevant so you should mention
that.

Unrelated but the first letter of your last name is unicode codepoint
3A4 which is the Greek upper case tau. Was this intentional or an
accident ?

On 19.04.2023 09:27, Martin Τrautmann wrote:
>
> Hi all,
>
> how do I sort by multiple columns?
>
> Example:
> +++
> Borgentreich;D9386;Lindenstätte;1;;32;520150.696;5709236.354
> Borgentreich;D9444;Auf der Lindenstätte;1;;32;519950.850;5708982.109
> Borgentreich;D9444;Auf der Lindenstätte;2;;32;519926.937;5708966.116
> Borgentreich;D9444;Auf der Lindenstätte;3;;32;520008.619;5709083.464
> Borgentreich;D9444;Auf der Lindenstätte;4;;32;519860.278;5709041.468
> Borgentreich;T2960;Lindenstätte;12;;32;519622.835;5709023.590
> Borgentreich;T2960;Lindenstätte;6;;32;519696.745;5709038.833
> Borgentreich;T2960;Lindenstätte;4;;32;519722.956;5709043.915
> Borgentreich;T2960;Lindenstätte;15;;32;519489.638;5709077.693
> Borgentreich;T2960;Lindenstätte;24;;32;519518.763;5709090.026
> Borgentreich;T2960;Lindenstätte;18;;32;519559.108;5709037.356
> Borgentreich;T2960;Lindenstätte;14;;32;519596.623;5709013.684
> Borgentreich;T2960;Lindenstätte;16;;32;519569.141;5709017.854
> Borgentreich;T2960;Lindenstätte;22;;32;519540.257;5709072.032
> Borgentreich;T2960;Lindenstätte;26;;32;519503.270;5709103.321
> Borgentreich;T2960;Lindenstätte;2;;32;519758.267;5709057.635
> Borgentreich;T2960;Lindenstätte;10;;32;519648.417;5709028.865
> Borgentreich;T2960;Lindenstätte;11;;32;519607.438;5708989.545
> Borgentreich;T2960;Lindenstätte;3;;32;519732.686;5709020.833
> Borgentreich;T2960;Lindenstätte;7;;32;519678.983;5709007.380
> Borgentreich;T2960;Lindenstätte;9;;32;519651.859;5709000.462
> Borgentreich;T2960;Lindenstätte;5;;32;519708.841;5709015.137
> Borgentreich;T2960;Lindenstätte;1;;32;519778.725;5709026.584
> Borgentreich;T2960;Lindenstätte;8;;32;519673.036;5709040.372
> +++
>
> I want to sort
> * first by column 4, numerical,
> * second by column 2
> * third by column 3

From that specification I'd write

sort -t\; -k4n -k2 -k3

but your expected data below doesn't follow your own spec. So the
specification probably needs a correction.

(Option -s for a "stable sort" may also be part of your solution.)

Janis

>
> So the result should be
> +++
> Borgentreich;D9444;Auf der Lindenstätte;1;;32;519950.850;5708982.109
> Borgentreich;D9444;Auf der Lindenstätte;2;;32;519926.937;5708966.116
> Borgentreich;D9444;Auf der Lindenstätte;3;;32;520008.619;5709083.464
> Borgentreich;D9444;Auf der Lindenstätte;4;;32;519860.278;5709041.468
> Borgentreich;D9386;Lindenstätte;1;;32;520150.696;5709236.354
> Borgentreich;T2960;Lindenstätte;1;;32;519778.725;5709026.584
> Borgentreich;T2960;Lindenstätte;2;;32;519758.267;5709057.635
> Borgentreich;T2960;Lindenstätte;3;;32;519732.686;5709020.833
> Borgentreich;T2960;Lindenstätte;4;;32;519722.956;5709043.915
> Borgentreich;T2960;Lindenstätte;5;;32;519708.841;5709015.137
> Borgentreich;T2960;Lindenstätte;6;;32;519696.745;5709038.833
> Borgentreich;T2960;Lindenstätte;7;;32;519678.983;5709007.380
> Borgentreich;T2960;Lindenstätte;8;;32;519673.036;5709040.372
> Borgentreich;T2960;Lindenstätte;9;;32;519651.859;5709000.462
> Borgentreich;T2960;Lindenstätte;10;;32;519648.417;5709028.865
> Borgentreich;T2960;Lindenstätte;11;;32;519607.438;5708989.545
> Borgentreich;T2960;Lindenstätte;12;;32;519622.835;5709023.590
> Borgentreich;T2960;Lindenstätte;14;;32;519596.623;5709013.684
> Borgentreich;T2960;Lindenstätte;15;;32;519489.638;5709077.693
> Borgentreich;T2960;Lindenstätte;16;;32;519569.141;5709017.854
> Borgentreich;T2960;Lindenstätte;18;;32;519559.108;5709037.356
> Borgentreich;T2960;Lindenstätte;22;;32;519540.257;5709072.032
> Borgentreich;T2960;Lindenstätte;24;;32;519518.763;5709090.026
> Borgentreich;T2960;Lindenstätte;26;;32;519503.270;5709103.321
> +++
>
> I tried both
> sort -k4 -t";" -n | sort -k2,2 -t";" | sort -k3,3 -t";"
> and
> sort -k4 -t";" -n -k2,2 -k3,3
> and some permutations and reverted orders, without success.
> The sort by column 4 just gets lost or resorted.
>
> I'm not sure about the man page
> -k, --key=POS1[,POS2]
> start a key at POS1, end it at POS2 (origin 1)
>
> So I tried relative positions with
> -k3,1
> as well, without success.
>
> How do I apply the sort syntax properly?
>
> Thanks
> Martin
>

On 19.04.2023 10:44, Janis Papanagnou wrote:
> On 19.04.2023 09:27, Martin Τrautmann wrote:
>>
>> Hi all,
>>
>> how do I sort by multiple columns?
>>[...]
>>
>> I want to sort
>> * first by column 4, numerical,
>> * second by column 2
>> * third by column 3
>
> From that specification I'd write
>
> sort -t\; -k4n -k2 -k3

Oops... - make that

sort -t\; -k4,4n -k2,2 -k3,3

>
> but your expected data below doesn't follow your own spec. So the
> specification probably needs a correction.

You probably meant something like

sort -t\; -k3,3 -k4,4n -k2,2

Janis

On Wed, 19 Apr 2023 08:43:15 -0000 (UTC), Spiros Bousbouras wrote:
>> So the result should be
>> +++
>> Borgentreich;D9444;Auf der Lindenstätte;1;;32;519950.850;5708982.109
> [...]
>> Borgentreich;D9386;Lindenstätte;1;;32;520150.696;5709236.354
>
> Why are these 2 lines sorted this way ? Column 4 is the same ("1" in
> both) so it boils down to how "D9444" and "D9386" get sorted. What
> comes first and why ? It seems to me that "D9386" comes earlier than
> "D9444" .

You took an example where both D9444 / D9386 and "Auf der Lindenstätte"
/ "Lindenstätte" differ.

> Your locale may also turn out to be relevant so you should mention
> that.

LANG=en_US.UTF-8
LC_ALL=en_US.UTF-8
LC_CTYPE=UTF-8

> Unrelated but the first letter of your last name is unicode codepoint
> 3A4 which is the Greek upper case tau. Was this intentional or an
> accident ?

unrelated - it's a check for proper UTF8 handling within headers.

On Wed, 19 Apr 2023 11:51:41 +0200, Janis Papanagnou wrote:
> On 19.04.2023 10:44, Janis Papanagnou wrote:
>> On 19.04.2023 09:27, Martin Τrautmann wrote:
> You probably meant something like
>
> sort -t\; -k3,3 -k4,4n -k2,2

Wow, that's just perfect. I did not know I can attach the n directly to
the key option

Thanks!
Martin

> Martin Τραωτμανν <t-usenet@gmx.net>:
>
> how do I sort by multiple columns?
>

[An example text…]

> I want to sort
> * first by column 4, numerical,
> * second by column 2
> * third by column 3

[…with sorted result]

The sorted result of your example has apparently been sorted
according to the following description:

First, group the lines sorted by column 3, that is, sort the
lines in a manner that results in alphabetically ascending values
in column 3.

Then, in each group of lines, that have got a common value in
column 3, sort the lines independently in a manner that results
in alphabetically ascending values in column 2.

Then, in each group of lines that have got common values in
columns 3 and 2 respectively, sort the lines independently in a
manner that results in numerically ascending values in column 4.

Finally, each group of lines that has got equal values in columns
3, 2, and 4 according to the sort criteria as specified above, is
sorted according to a default sorting criterium which comprises
the whole line.

This can be achieved using the following commandline:

sort -t ';' -k 3,3 -k 2,2 -k 4,4n

You might read the description of the "sort" utility in the POSIX
standard
(<https://pubs.opengroup.org/onlinepubs/9699919799/utilities/sort.html#top>),
especially the last paragraph in the "OPTIONS" section
(<https://pubs.opengroup.org/onlinepubs/9699919799/utilities/sort.html#tag_20_119_04>): 
"When there are multiple key fields, later keys shall be compared
only after all earlier keys compare equal.  Except when the -u
option is specified, lines that otherwise compare equal shall be
ordered as if none of the options -d, -f, -i, -n, or -k were
present (but with -r still in effect, if it was specified) and
with all bytes in the lines significant to the comparison.  The
order in which lines that still compare equal are written is
unspecified."

On Sat, 22 Apr 2023 03:33:43 +0200, Helmut Waitzmann wrote:
>> I want to sort
>> * first by column 4, numerical,
>> * second by column 2
>> * third by column 3
>
> […with sorted result]
>
>
> The sorted result of your example has apparently been sorted
> according to the following description:
>
> First, group the lines sorted by column 3, that is, sort the
> lines in a manner that results in alphabetically ascending values
> in column 3.

That's a matter of concern how the sort works.

If I want to pre-sort by 3 first, then sub-sort by column 2, that's
fine. But when I pipe one sort to the other, the second sort will
destroy the sort before. That's why i had my sort order in reverted
order, using a pipe example.

If all sorts can be done within a single command, the direct order works
better. I had not been aware of the direkt -k4,4n option, while the -n
option could not be applied by me as desired.

> You might read the description of the "sort" utility in the POSIX
> standard
> (<https://pubs.opengroup.org/onlinepubs/9699919799/utilities/sort.html#top>),
> especially the last paragraph in the "OPTIONS" section
> (<https://pubs.opengroup.org/onlinepubs/9699919799/utilities/sort.html#tag_20_119_04>): 
> "When there are multiple key fields, later keys shall be compared
> only after all earlier keys compare equal.  Except when the -u
> option is specified, lines that otherwise compare equal shall be
> ordered as if none of the options -d, -f, -i, -n, or -k were
> present (but with -r still in effect, if it was specified) and
> with all bytes in the lines significant to the comparison.  The
> order in which lines that still compare equal are written is
> unspecified."

This description is much better than my man and info sort - but
unfortunately I can't be sure that the POSIX info actually does work on
my local sort implementation:
sort 5.93 November 2005

AUTHOR
Written by Mike Haertel and Paul Eggert.

REPORTING BUGS
Report bugs to <bug-coreutils@gnu.org>.

COPYRIGHT
Copyright (C) 2005 Free Software Foundation, Inc.

Martin Τrautmann <t-usenet@gmx.net>:
> On Sat, 22 Apr 2023 03:33:43 +0200, Helmut Waitzmann wrote:
>>> I want to sort
>>> * first by column 4, numerical,
>>> * second by column 2
>>> * third by column 3
>>
>> […with sorted result]
>>
>>
>> The sorted result of your example has apparently been sorted
>> according to the following description:
>>
>> First, group the lines sorted by column 3, that is, sort the
>> lines in a manner that results in alphabetically ascending
>> values in column 3.
>
> That's a matter of concern how the sort works.
>
>
> If I want to pre-sort by 3 first, then sub-sort by column 2,
> that's fine. But when I pipe one sort to the other, the second
> sort will destroy the sort before. That's why i had my sort
> order in reverted order, using a pipe example.

That won't help, either:  A sorting pipe using (a standard)
"sort" won't solve the problem, because one cannot tell (a
standard) "sort" to do a sort on the given key option only.  Each
sort in the pipe will be total (according to its sort criteria)
of its own.

With GNU‐"sort", though, a sorting pipe can solve the problem, if
one applies the "--stable" option to each (except the first) of
the "sort" invocations.  Then the command

sort --stable -t ';' -n -k 4,4 |
sort --stable -t ';' -k 2,2 |
sort --stable -t ';' -k 3,3

will do the job.  (Unfortunately the "--stable" option is not
part of the POSIX standard.)

[A quote from the "sort" description in the POSIX standard]

> This description is much better than my man and info sort
>

Yes, that's my experience, too.  I tend to read not only the
manual page or info documentation but also look into the
corresponding POSIX description (if the utility is part of the
POSIX standard), and then check, whether the manual page or info
documentation conflicts with the POSIX description.

> - but unfortunately I can't be sure that the POSIX info actually
> does work on my local sort implementation: sort 5.93 November
> 2005

Yes, that might happen.  In practice, GNU tries to follow the
POSIX standard.

In article <op.13uwd4i8a3w0dxdave@hodgins.homeip.net>,
David W. Hodgins <dwhodgins@nomail.afraid.org> wrote:
....
>Keep in mind. When sorting a file, the last line in the input may end up
>becoming the first line in the output. The sort can not write anything to
>the pipe or output file until it's sorted the entire input. With a pipe,
>the temporary file is in ram rather then being a named file on disk.

This actually raises an interesting point. Pipes are not infinite in size,
and they could, theoretically block if enough is written on the write end
without anything being read from the read end. Though the limits are
likely very large nowadays on modern systems, I think the original
implementation was only 4096 bytes and the standards today (POSIX) may not
guarantee anything more than that (haven't checked).

For most programs, this is rarely a concern, since most pipelines write and
read more or less simultaneously in real time, but sort is an edge case for
the reason you explain above.

Something to keep in mind if you ever decide to sort very large files in a
pipeline. And it is probably a better idea not to do so; to sort it all at
once, using multiple key specifications on the command line.

--
Rich people pay Fox people to convince middle class people to blame poor people.

(John Fugelsang)

On 23.04.2023 16:36, Kenny McCormack wrote:
> [...]
>
> For most programs, this is rarely a concern, since most pipelines write and
> read more or less simultaneously in real time, but sort is an edge case for
> the reason you explain above.

Note also that there are quite some sorting operations inherently
used (e.g. in 'ls', in shells '*' glob/pattern expansion, etc.).
For example, don't expect find | xargs ls to provide a sorted
output.

>
> Something to keep in mind if you ever decide to sort very large files in a
> pipeline. [...]

In whatever way some instance of sort is implemented (memory, or
temporary files, or whatever), my expectation is that
whatever | sort
will have to produce sorted output .- Isn't that guaranteed?

Janis

On 2023-04-23, Kenny McCormack <gazelle@shell.xmission.com> wrote:
> The bad case would be if a program produced a ton of output, but the reader
> didn't read any of it. I'll have to think some more as to whether or not
> that applies here.

Limited pipe sizes cause two potential problems:

- deadlock: programs that both read and write a pipe may work when
tested with small messages, but lock up on larger ones.

- atomicity of writes: a write of a number of bytes smaller
than the pipe size can be read all together on the other end,
so the reading end will work correctly without checking for
a short read. When the message size exceeds the pipe size,
that breaks.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca

On Sun, 23 Apr 2023 14:36:30 -0000 (UTC)
gazelle@shell.xmission.com (Kenny McCormack) wrote:
> In article <op.13uwd4i8a3w0dxdave@hodgins.homeip.net>,
> David W. Hodgins <dwhodgins@nomail.afraid.org> wrote:
> ...
> >Keep in mind. When sorting a file, the last line in the input may end up
> >becoming the first line in the output. The sort can not write anything to
> >the pipe or output file until it's sorted the entire input. With a pipe,
> >the temporary file is in ram rather then being a named file on disk.
>
> This actually raises an interesting point. Pipes are not infinite in size,
> and they could, theoretically block if enough is written on the write end
> without anything being read from the read end. Though the limits are
> likely very large nowadays on modern systems, I think the original
> implementation was only 4096 bytes and the standards today (POSIX) may not
> guarantee anything more than that (haven't checked).

I tried to find an argument which you can give to getconf to get the
answer to that but I didn't see anything. I don't think POSIX gives a constant
(in some C header) to get the answer to that. There is PIPE_BUF but this is
for atomic writes rather than total pipe capacity.

> For most programs, this is rarely a concern, since most pipelines write and
> read more or less simultaneously in real time, but sort is an edge case for
> the reason you explain above.
>
> Something to keep in mind if you ever decide to sort very large files in a
> pipeline. And it is probably a better idea not to do so; to sort it all at
> once, using multiple key specifications on the command line.

I don't see the problem. If sort is on the left of a pipe then it will
sort its whole input and then all it will do is write to the pipe. If sort
is on the right of a pipe then in the beginning it will only do reading
until it has read everything and then do the sorting. Obviously if you
have process1 | process2 and one side does reading or writing (whatever
applies) much slower than the other side then the fast side will block but
there's nothing special with sort about that. On the contrary , by the
nature of what it does , sort will only do reading or writing during part
of its operation.

--
Fans of both doomsday scenario movies and movies that show close-ups of Willem
Dafoe's pubic region should walk away eerily pleased from this one.
https://www.imdb.com/review/rw2553866/

* Kenny McCormack <gazelle@shell.xmission.com>:
> David W. Hodgins <dwhodgins@nomail.afraid.org> wrote:
> ...
>>Keep in mind. When sorting a file, the last line in the input may end up
>>becoming the first line in the output. The sort can not write anything to
>>the pipe or output file until it's sorted the entire input. With a pipe,
>>the temporary file is in ram rather then being a named file on disk.
>
> This actually raises an interesting point. Pipes are not infinite in size,
> and they could, theoretically block if enough is written on the write end
> [...]
> Something to keep in mind if you ever decide to sort very large files in a
> pipeline. And it is probably a better idea not to do so; to sort it all at
> once, using multiple key specifications on the command line.

This won't be a concern here. You need the whole data to sort something,
so the sort utility must read until EOF anyways before doing its work.
So, the real concern is whether you'll have enough RAM.

The only alternative would be to sort on the file contents. I don't know
whether some sort utility can do that (it certainly would create other
issues when sorting by "text lines" of very different lengths), but
that's not possible with pipes anyways, they can't be seeked.

--
Dipl.-Inform. Felix Palmen <felix@palmen-it.de> ,.//..........
{web} http://palmen-it.de {jabber} [see email] ,//palmen-it.de
{pgp public key} http://palmen-it.de/pub.txt // """""""""""
{pgp fingerprint} 6936 13D5 5BBF 4837 B212 3ACC 54AD E006 9879 F231

On Sun, 23 Apr 2023 10:36:30 -0400, Kenny McCormack <gazelle@shell.xmission.com> wrote:
> This actually raises an interesting point. Pipes are not infinite in size,
> and they could, theoretically block if enough is written on the write end
> without anything being read from the read end. Though the limits are
> likely very large nowadays on modern systems, I think the original
> implementation was only 4096 bytes and the standards today (POSIX) may not
> guarantee anything more than that (haven't checked).

Just tested "sort bigfile|hexdump|less". htop shows it's using 917M of ram
and 2.5GB of virtual storage (reserved, not all used) to sort a 730M input
file.

After ending the less output ...
$ free -m
total used free shared buff/cache available
Mem: 15955 5715 2376 361 7863 9548
Swap: 32761 2 32758

There may be versions of sort that are still limit how much ram it can use but
the version from the coreutils packages is not one of them. It's only limit is
based on the amount of ram and swap space available, and what the oom killer
can make available if you do start to run out.

Also note it has options such as "--temporary-directory=DIR" to use disk files
for temporary storage instead of ram.

Regards, Dave Hodgins

On 23.04.2023 18:36, Richard Harnden wrote:
>
> My man page says:

Thanks for that, since my man page doesn't say anything about the
algorithms. Now we have some clue what 'sort' on Unix does; and it
seems that hybrid sorting algorithms aren't implemented; which is
really strange since Quicksort implementations usually use Linear
Sort for small partitions, and upthread I already spoke about the
Mergesort/Heapsort hybrid. (Room for improvement? Or are they just
presuming that everything is doable with an arbitrary large virtual
memory? Who knows.)

>
> --radixsort
> Try to use radix sort, if the sort specifications allow.
> The radix sort can only be used for trivial locales (C and
> POSIX), and it cannot be used for numeric or month sort.
> Radix sort is very fast and stable.
>
> --mergesort
> Use mergesort. This is a universal algorithm that can
> always be used, but it is not always the fastest.
>
> --qsort
> Try to use quick sort, if the sort specifications allow.
> This sort algorithm cannot be used with -u and -s.
>
> --heapsort
> Try to use heap sort, if the sort specifications allow.
> This sort algorithm cannot be used with -u and -s.
>

Janis

On Sun, 23 Apr 2023 19:16:25 +0200
Janis Papanagnou <janis_papanagnou+ng@hotmail.com> wrote:
> On 23.04.2023 18:58, Felix Palmen wrote:
> > * Janis Papanagnou <janis_papanagnou+ng@hotmail.com>:
> >> On 23.04.2023 18:21, Felix Palmen wrote:
> >>>
> >>> This won't be a concern here. You need the whole data to sort something,
> >>> so the sort utility must read until EOF anyways before doing its work.
>
> s/doing/finishing/
>
> >> See my recent reply on a different view.
> >
> > So, even if it starts working on "chunks", this won't change anything:
> > the data from the pipe must be read in order to work with it, so the
> > size of the pipe won't be a problem here.
> >
> > It seems the idea assuming this was that the whole data to be sorted
> > must fit into the pipe buffer. But this isn't the case.
>
> It boils down to this; sorting can _start_ sorting with fewer data
> (something like a pipe-full), it can also _continue_ sorting with
> more parts of data, and to _finish_ sorting it naturally must have
> had all data available.

I think Kenny was worried in <u23fpe$2opsm$1@news.xmission.com>
and <u23ito$2osbe$1@news.xmission.com> about a deadlock situation where
no progress gets made because of low pipes capacity. I can't think of
a scenario where this can happen even if sort interleaves sorting and
reading from a pipe.

On 4/23/23 10:36, Kenny McCormack wrote:
> This actually raises an interesting point. Pipes are not infinite in size,
> and they could, theoretically block if enough is written on the write end
> without anything being read from the read end. Though the limits are
> likely very large nowadays on modern systems, I think the original
> implementation was only 4096 bytes and the standards today (POSIX) may not
> guarantee anything more than that (haven't checked).

FWIW, the pipe(7) manpage from Debian GNU/Linux has a "Pipe capacity"
section that says in part:

Before Linux 2.6.11, the capacity of a pipe was the same as the
system page size (e.g., 4096 bytes on i386). Since Linux
2.6.11, the pipe capacity is 16 pages (i.e., 65,536 bytes in a
system with a page size of 4096 bytes). Since Linux 2.6.35,
the default pipe capacity is 16 pages, but the capacity can be
queried and set using the fcntl(2) F_GETPIPE_SZ and F_SET‐
PIPE_SZ operations. See fcntl(2) for more information.

So pipes on Linux aren't very large at all. I don't know how other Unix
systems compare.

Martin Τrautmann <t-usenet@gmx.net>:
> On Sun, 23 Apr 2023 03:33:47 +0200, Helmut Waitzmann wrote:
>>> If I want to pre-sort by 3 first, then sub-sort by column 2,
>>> that's fine. But when I pipe one sort to the other, the second
>>> sort will destroy the sort before. That's why i had my sort
>>> order in reverted order, using a pipe example.
>>
>> That won't help, either:  A sorting pipe using (a standard)
>> "sort" won't solve the problem, because one cannot tell (a
>> standard) "sort" to do a sort on the given key option only. 
>> Each sort in the pipe will be total (according to its sort
>> criteria) of its own.
>
> That was my problem - I expected that a pipe through several
> sorts would keep the order. I don't know why it doesn't.

Look at these sample lines:

1;0
1;1
1;2
0;0
0;1
0;2
2;0
2;1
2;2

To have this sequence of lines sorted in such a way that the
first field is sorted in ascending numeric order while the second
is sorted in descending numeric order, one could specify the two
sort criteria at once:

sort -t ';' -k 1nb,1 -k 2nr,2

How would the command line be if one would use two "sort"
invocations with each of them getting only one "-k" option
(replacing the "???" by the appropriate sort key specifications)?

first=??? ; second=???
sort -t ';' -k "$first" |
sort -t ';' -k "$second"

Or (if it's easier to understand, but it's equivalent) use an
intermediate file rather than a pipe:

first=??? ; second=???
sort -t ';' -k "$first" > file &&
sort -t ';' -k "$second" -- file

Try to answer the following questions:

Would the variable assignments

first=2nr,2
second=1nb,1

yield the correct result?  Why or why not?  Would they work if
one adds the GNU‐"sort" "--stable" option to the second "sort"
invocations?  Why or why not?

When using the variant with the intermediate file, after having
run the first "sort" invocation, you might examine the
intermediate file and try to predict what would be the outcome of
the second "sort" invocation.

On Sun, 23 Apr 2023 15:42:00 -0400, John-Paul Stewart <jpstewart@personalprojects.net> wrote:
> So pipes on Linux aren't very large at all. I don't know how other Unix
> systems compare.

The pipe only has to store a minimum of one buffer of data. If the process
writing data to the pipe is faster than the one reading it, then the write
process will block while it waits for the reading process to catch up.
Likewise if the reading process is faster. It will just block while it waits
for the data to be ready.

Having more buffers will speed it up only the processes run at different
speeds with the slower one being inconsistent in it's speed.

A good example of that is sort somefile>less.

If the the user presses page down repeatedly. Each time the faster sort process
has written enough data to fill the buffers, it gets blocked from writing until
the page down key is pressed and the less command reads the data for the next
screen full, freeing up some of the buffer space.

Note that when I write that the sort command is faster, by time the first
screen full shows up in less, all of the data has been sorted, it just needs
to be written to the output. Until the data is sorted, the less command is
blocked, waiting for input.

Regards, Dave Hodgins

On Sun, 23 Apr 2023 12:58:41 -0400, Felix Palmen <felix@palmen-it.de> wrote:
> It seems the idea assuming this was that the whole data to be sorted
> must fit into the pipe buffer. But this isn't the case.

As the last line of the input file(s) may be the first line of the final output,
all of the data must be sorted before anything is written to the pipe.

Either all of the data has to fit in ram, or it has to be sorted in chunks
with those chunks stored on disk, and then the chunks are then merged to
produce the output.

The coreutils package's sort can use temporary (unamed) files as needed in the
directory specified by the TMPDIR environment variable. (/tmp on most systems).
They wont show up in ls as they are unnamed.

It's not clear from the man page if it will always use temporary files or only
if instructed to. So checking the source ...
https://git.savannah.gnu.org/gitweb/?p=coreutils.git;a=blob;f=src/sort.c;h=8ca7a88c48ec07eccd952b14739e427721466c5d;hb=HEAD

If I'm reading it right, it always uses temporary files doing a sort/merge.
Given that it started in 1988, it's not surprising that it's designed to work
in a low ram environment.

So if you're in a low ram environment either ensure the $TMPDIR directory is
not in ram, or include the --temporary-directory=DIR to specify another
directory that is on a disk file system with enough free space.

Regards, Dave Hodgins

On Sun, 23 Apr 2023 15:42:00 -0400, John-Paul Stewart wrote:

> On 4/23/23 10:36, Kenny McCormack wrote:
>> This actually raises an interesting point. Pipes are not infinite in size,
>> and they could, theoretically block if enough is written on the write end
>> without anything being read from the read end. Though the limits are
>> likely very large nowadays on modern systems, I think the original
>> implementation was only 4096 bytes and the standards today (POSIX) may not
>> guarantee anything more than that (haven't checked).
>
> FWIW, the pipe(7) manpage from Debian GNU/Linux has a "Pipe capacity"
> section that says in part:
>
> Before Linux 2.6.11, the capacity of a pipe was the same as the
> system page size (e.g., 4096 bytes on i386). Since Linux
> 2.6.11, the pipe capacity is 16 pages (i.e., 65,536 bytes in a
> system with a page size of 4096 bytes). Since Linux 2.6.35,
> the default pipe capacity is 16 pages, but the capacity can be
> queried and set using the fcntl(2) F_GETPIPE_SZ and F_SET‐
> PIPE_SZ operations. See fcntl(2) for more information.

And fcntl(2) says
F_SETPIPE_SZ (int; since Linux 2.6.35)
Change the capacity of the pipe referred to by fd to be at least
arg bytes. An unprivileged process can adjust the pipe capacity
to any value between the system page size and the limit defined
in /proc/sys/fs/pipe-max-size (see proc(5)).

On my Linux (untuned 4.4.301 kernel), /proc/sys/fs/pipe-max-size
is set to
16:35 $ cat /proc/sys/fs/pipe-max-size
1048576
or 1Mb

> So pipes on Linux aren't very large at all.

.... unless you tune them upward.

> I don't know how other Unix systems compare.

I've seen some studies; Linux pipe buffer sizes seem comparable to
other systems, which range in the 20K to 64K default size range, and
top out at about 1Mb.

HTH
--
Lew Pitcher
"In Skills We Trust"

Helmut Waitzmann <nn.throttle@xoxy.net>:
> Look at these sample lines:
>
>
> 1;0
> 1;1
> 1;2
> 0;0
> 0;1
> 0;2
> 2;0
> 2;1
> 2;2
>
>
> To have this sequence of lines sorted in such a way that the
> first field is sorted in ascending numeric order while the
> second is sorted in descending numeric order,

I'm sorry, that is a quite misleading description.  What I wanted
to say is that the sequence of lines should be sorted to look
like

0;2
0;1
0;0
1;2
1;1
1;0
2;2
2;1
2;0

and to achieve this…

> one could specify the two sort criteria at once:
>
> sort -t ';' -k 1nb,1 -k 2nr,2

On Sun, 23 Apr 2023 03:33:47 +0200, Helmut Waitzmann wrote:
>> If I want to pre-sort by 3 first, then sub-sort by column 2,
>> that's fine. But when I pipe one sort to the other, the second
>> sort will destroy the sort before. That's why i had my sort
>> order in reverted order, using a pipe example.
>
> That won't help, either:  A sorting pipe using (a standard)
> "sort" won't solve the problem, because one cannot tell (a
> standard) "sort" to do a sort on the given key option only.  Each
> sort in the pipe will be total (according to its sort criteria)
> of its own.

That was my problem - I expected that a pipe through several sorts would
keep the order. I don't know why it doesn't.

On Sun, 23 Apr 2023 07:28:22 -0400, Martin Τrautmann <t-usenet@gmx.net> wrote:
> That was my problem - I expected that a pipe through several sorts would
> keep the order. I don't know why it doesn't.

It may be easier to understand if you use a temporary files instead of pipes.

Sorting the input file by column 4, numerical creating a first temporary file.
Sort the first temporary file by column 2 creating a second temporary file.
Sort the second temporary file by column 3 creating the output.

The last sort doesn't know that the prior two sorts have been done. It just
looks at the file it's giving and sorts it by column 3.

Using a pipe just takes the output of the first and second sort and uses it
directly as input for the next sort. All the pipe does is eliminate the
need for a temporary file.

Keep in mind. When sorting a file, the last line in the input may end up becoming
the first line in the output. The sort can not write anything to the pipe or
output file until it's sorted the entire input. With a pipe, the temporary
file is in ram rather then being a named file on disk.

Regards, Dave Hodgins