Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: Richard Heathfield <rjh@cpax.org.uk>
Newsgroups: comp.theory
Subject: LineSort
Date: Mon, 9 Jun 2025 21:37:08 +0100
Organization: Fix this later
Lines: 53
Message-ID: <1027gln$ofnf$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Mon, 09 Jun 2025 22:37:11 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="3a258d3dafd76d192376f6638c35cda2";
	logging-data="802543"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/suykvAWKCmALK1RIBhCwL9miFUSrkWsDTfwQNhyhkDA=="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:wToIDS3JGJGFQiNHKGqkfYG1fwk=
Content-Language: en-GB

I have no doubt that I am not the first one here to reinvent 
several wheels (my biggest wheel was AVL tree-balancing, but it's 
by no means the only one).

So, if a Web search turns nothing up, how does one know that one 
has been beaten to the punch?

One asks around, of course... so I'm asking.

Consider a set of n unequal items, such that EITHER Charles > 
Lisa OR Lisa > Charles. You are NOT ABLE to compare two items 
directly, but you are given enough ordered pairings that you can 
reconstruct the proper order of the set.

I devised a solution ('LineSort') for this problem, and my 
question is simply whether prior art beat me to it.

Place the items in arbitrary order. Starting at the back B, work 
through the pairings looking for an item A that is currently 
ahead of B but belongs somewhere behind it, and do this:

1. cdefAghijkB

2. cdef_ghijkB

3. cdefghijkB_

4. cdefghijkBA

Keep going through all your pairings, looking for an item that 
you can dislodge because it belongs behind B; everybody (back to 
B) shuffles up one place, and the dislodged item goes in the 
place that B vacates.

When you've run out of pairings, go round again, this time 
starting with the item in front of B.

Once you're starting at the front, obviously you have to stop. 
That's one pass.

Make as many passes as you need to until no movements occur 
throughout the pass.

Clearly this is fairly easy to de-pessimise, but my question is 
whether there is prior art for the general approach.

Any ideas?

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within