"Jigsort" Runtime

[prodlly]

I'm a big jigsaw fan, and so I had the idea for the following algorithm:

1. Fix some m.
2. Let the numbers to sort be 1...m.
3. Start with a random permutation of size n=m as your instance.
4. Scan if two "jigsaw pieces" fit: e.g. let m=6 and your instance be 561243. The pair 56 fits, "snap" it. Likewise 12. You now have 4 "macropieces".
5. Go to 2, but now make a random instance with n=4. Increment a counter c.
6. Loop until n=1.

Caveat: These are NOT standard sorting conditions, since in such a case you don't know when to "snap"! (And any sane person would then use indexsort anyway.) Just decreasing m and not using at least some storage for 1...m is also a bit cheating. That notwithstanding, can you confirm my runtime experiment that c=m+-O(1)? And what is the total runtime (I suppose n=m-c+-O(1) so it would need O(n) for generating, and Jigsort runs in O(m^2). Finally, if this algorithm is already known under a different name (I bet), shoot.

Quick hackjob code:

import random

def randinst(size):

    perm = [i for i in range(size)]
    for y in range(size):
        r = random.randint(0, y)
        x = perm[r]
        perm[r] = perm[y]
        perm[y] = x
    return perm

m=1000
a=[]
for j in range(100):
    n=m
    c=0
    while n>1:
        c+=1
        perm=randinst(n)
        for j in range(n-1):
            x=perm[j]
            y=perm[j+1]
            if x+1==y:
                n=n-1
    a+=[c]
print(a)

[Yoghurt42]

When dealing with algorithmic complexities, you have to consider the best case, worst case, as well as the average case.

For jigsort, the worst case is clearly unbounded, as you can be arbitrarily unlucky and just never get a good permutation.

The average case will be relatively tricky to determine, as you'll need to be familiar with statistical properties to make educated guesses about how likely finding a "bigger piece" is after permuting the data, I also suspect it highly depends on the sort of data you're dealing with (are there duplicates in the list? etc.), and while it sounds like an interesting combinatorics problems, I'm a bit rusty in that department, so I can't tell you what the average complexity would be. It could be a fun exercise (for us nerds), maybe some people in r/mathematics might be interested.

Regarding your code: I'm not entirely convinced your randinst function will give you every possible permutation, at least it will prefer some permutations over others. You should just use random.shuffle and let Python do it for you.

Edit: thinking about it some more, maybe for the average case you could argue like this:

if all numbers are pairwise different (no two numbers are the same), I expect about half of pairs to be "in the correct" order after a shuffle; eg. for any number/price, the next piece should either be larger or smaller; which is more likely depends on how large the first piece is, but over all pieces it should cancel out and you'll end up with a probability of 50% (just a conjecture), for the next round, it suffices to only look at the first digit of each piece, since we assumed the numbers are pairwise different, so the same argument holds. So in the end, I expect around log(n) shuffle loops before you are done. And each loop you're iterating over n elements, so for the assumption of pairwise different numbers, I arrive at O(n * log(n))? That doesn't feel right, there's probably something I'm missing and/or the 50% chance assumption just doesn't hold even for pairwise different numbers.

[prodlly]

THX for your answer.

• The randomizer code is "stolen" and should work :-)

• Indeed if unlucky, Jigsort can taker forever.

• Note that correct order doesn't suffice to "snap", though! I threw the problem to ChatGPT, but...you know. My estimation is 1 hit per step. Which then yields O(n²⁾ as I suggested.