Re: sorting Was: Isn't that beauty ? (no it's not)

Path	csiph.com!eternal-september.org!feeder.eternal-september.org!nntp.eternal-september.org!.POSTED!not-for-mail
From	Tim Rentsch <tr.17687@z991.linuxsc.com>
Newsgroups	comp.lang.c
Subject	Re: sorting Was: Isn't that beauty ? (no it's not)
Date	Sun, 12 Apr 2026 06:17:12 -0700
Organization	A noiseless patient Spider
Lines	35
Message-ID	<86wlyc8giv.fsf@linuxsc.com> (permalink)
References	<10otm7r$1ntrg$1@raubtier-asyl.eternal-september.org> <86mrzfxvv5.fsf@linuxsc.com> <10r35bp$29m9s$1@paganini.bofh.team> <863416xid5.fsf@linuxsc.com> <10r94t2$or8$1@reader1.panix.com> <20260410013139.000059d4@yahoo.com>
MIME-Version	1.0
Content-Type	text/plain; charset=us-ascii
Injection-Date	Sun, 12 Apr 2026 13:17:15 +0000 (UTC)
Injection-Info	dont-email.me; posting-host="425f3de481b107cac4c4e410f9a2c2b8"; logging-data="2689433"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19SxWbz2ghM0B34V1RC/sbJEtRlwgsttlE="
User-Agent	Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux)
Cancel-Lock	sha1:SoeDyYB/Iwb+68rfr0lruKeEVow= sha1:lekvQno8hVQWsjH26jMzLxXW964=
Xref	csiph.com comp.lang.c:397502

Show key headers only | View raw

Michael S <already5chosen@yahoo.com> writes:

> On Thu, 9 Apr 2026 21:15:14 -0000 (UTC)
> cross@spitfire.i.gajendra.net (Dan Cross) wrote:
[...]
>> Indeed.  As Rob Pike once put it, "Fancy algorithms are slow
>> when $n$ is small, and $n$ is usually small.  Fancy algorithms
>> have big constants.  Until you know that $n$ is frequently going
>> to get big, don't get fancy."
>
> One case where these considerations are not at all theoretical and
> where simple quicksort from the books performs very very slowly exactly
> because when sorting progresses each lexicographic comparison
> takes more and more time, is a sorting at core of Burrows-Wheeler
> transform, which in turn is at core of various compression schemes,
> including bzip2.  The problem hits you the worst when data set compresses
> well.

I'm curious to know if you can quantify this to some degree, and
if so how much.  I don't have any experience with Burrows-Wheeler
transform or (any internals of) bzip2.

> In specific case of bzip2, they limited block size to 900KB which
> is quite low and did preprocessing on input data which often seriously
> impacts the quality of compression.  I can't say for sure, but it seems
> to me that the reason was exactly that - avoiding prohibitively slow
> sorting.  Were they had time and desire to use "fancy algorithms",
> either combinations of bucket and non-bucket variants of radix sort, or
> quicksort that memorizes common prefixes, or even combination of all
> three, then they would not need to use preprocessing and small blocks
> and would end up with better compression ratios.

There could be other reasons for wanting to limit the block size.
Have you done any web searches or tried to investigate in some
other ways?

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 16:43 -0400
  Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-16 20:57 +0000
    Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:07 -0400
      Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-17 00:49 +0000
        Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 05:21 +0100
          Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-18 12:40 -0400
            Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 17:06 +0000
              Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-18 15:46 -0400
                Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 22:14 +0000
          Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-19 22:39 +0000
        Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-18 16:14 -0400
          Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-19 22:42 +0000
      Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-17 14:46 +0000
  Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-16 22:26 +0000
    Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-16 22:35 +0000
    Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:09 -0400
      Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-16 23:17 +0000
        Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:21 -0400
          Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-16 23:34 +0000
            Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-17 00:09 +0000
              Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 21:45 -0400
                Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-17 10:42 +0000
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 13:04 +0100
                Re: Isn't that beauty ? (no it's not) Richard Harnden <richard.nospam@gmail.invalid> - 2026-03-17 12:17 +0000
                Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 12:31 +0000
            Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 21:27 -0400
  Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-16 22:26 +0000
    Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-16 19:41 -0400
      Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 00:29 +0000
        Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 05:38 +0100
          Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 11:47 +0000
            Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-17 13:08 +0100
              Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-17 12:37 +0000
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 02:40 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-18 11:21 +0200
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 10:49 +0100
                Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 15:10 +0000
                Re: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-18 21:20 +0000
                Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-18 23:13 +0000
                Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 13:23 -0700
                Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-18 11:20 +0100
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 21:57 +0100
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-18 22:01 +0100
                Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-19 10:43 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 12:23 +0200
                Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-19 15:22 +0100
                Re: Isn't that beauty ? (no it's not) scott@slp53.sl.home (Scott Lurndal) - 2026-03-19 15:07 +0000
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 04:16 +0100
                Re: Isn't that beauty ? (no it's not) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-03-20 02:14 -0700
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 12:38 +0100
                Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-20 13:06 +0100
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 13:27 +0100
                Re: Isn't that beauty ? (no it's not) Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2026-03-20 13:22 -0700
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-21 02:25 +0100
                Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-19 16:13 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 17:41 +0200
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 04:01 +0100
                Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-20 08:35 +0100
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 12:47 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 14:42 +0200
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:39 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-22 08:33 +0200
                Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-20 17:10 -0400
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-21 02:53 +0100
                Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-20 22:35 -0400
                Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-21 14:42 +0000
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:57 +0100
                Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 12:32 -0700
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:50 +0100
                Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-21 15:39 +0100
                Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-03-22 15:48 -0400
                Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-22 23:04 +0100
                Re: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-19 13:28 +0000
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 03:45 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 11:19 +0200
                Re: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-19 10:49 +0100
                Re: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-19 14:09 +0000
                Re: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-19 14:49 +0000
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 17:09 +0200
                sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 17:29 +0200
                Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-19 18:33 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-19 21:40 +0200
                Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-19 23:53 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-20 00:15 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 05:05 +0100
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 12:58 +0200
                Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 12:53 +0100
                Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 13:13 +0100
                Re: sorting Was: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-20 13:26 +0100
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 15:08 +0200
                Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-03-20 13:43 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 15:51 +0200
                Re: sorting Was: Isn't that beauty ? (no it's not) David Brown <david.brown@hesbynett.no> - 2026-03-20 14:47 +0100
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-22 02:03 +0200
                Re: sorting Was: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 04:03 +0100
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 15:13 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 02:22 +0300
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 21:00 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 09:37 +0300
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 21:54 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-09 16:06 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 09:04 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-11 19:55 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-04-07 14:46 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 20:04 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-09 21:15 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-10 01:31 +0300
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-12 06:17 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-11 21:32 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-12 04:59 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-26 07:29 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-04-09 23:33 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-10 11:35 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-12 07:13 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) cross@spitfire.i.gajendra.net (Dan Cross) - 2026-04-13 20:44 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-25 15:47 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 14:01 +0200
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 13:48 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 01:58 +0300
                Re: sorting Was: Isn't that beauty ? (no it's not) Bart <bc@freeuk.com> - 2026-04-07 01:02 +0100
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 08:01 -0700
                Re: sorting Was: Isn't that beauty ? (no it's not) antispam@fricas.org (Waldek Hebisch) - 2026-03-19 23:21 +0000
                Re: sorting Was: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-06 18:37 -0700
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-20 04:33 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-20 14:24 +0200
                Re: Isn't that beauty ? (no it's not) Janis Papanagnou <janis_papanagnou+ng@hotmail.com> - 2026-03-22 05:06 +0100
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-03-22 09:30 +0200
                Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-07 02:12 -0700
                Re: Isn't that beauty ? (no it's not) Michael S <already5chosen@yahoo.com> - 2026-04-07 14:00 +0300
                Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-16 10:23 -0700
                Re: Isn't that beauty ? (no it's not) DFS <nospam@dfs.com> - 2026-04-07 16:39 -0400
                Re: Isn't that beauty ? (no it's not) Tim Rentsch <tr.17687@z991.linuxsc.com> - 2026-04-12 11:16 -0700
                Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-25 00:45 +0000
  Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-17 06:25 +0100
    Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-20 01:33 +0000
      Re: Isn't that beauty ? (no it's not) Bonita Montero <Bonita.Montero@gmail.com> - 2026-03-20 07:42 +0100
        Re: Isn't that beauty ? (no it's not) Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2026-03-20 12:16 +0000

csiph-web