The Sorting Demon

I must have watched too many videos of graphical sorting algorithm visualisations. These are hypnotic... I'm so impressed by radix sort and bucket sort, and all the others have a very good lesson in algorithmics to give. But there is always this voice in your head that says, without telling how or why, that "there must be a better way" for simpler situations, which explains why there are so many sorting algorithms out there, and sorting is used in many places so why resist...

I was looking at the Fibonacci Heap algorithm and wondered how it could be turned into a sorting algorithm, so... nah. I want something much simpler. And it seems I have devised something that borrows from many domains. It is probably not the best (radix sort being the best ever, yeah) but "at least it's mine and i know how to do it" (a variant on the NIH syndrome). It may already exist under a name I don't know, but do I care ?

It is based around the merge sort principle, which I love due to its simplicity, but I want it to work well both on totally random and on sorted inputs. So it has 2 stages :

• First : scan the incoming sequence for an ascending, then a descending sequence. Once they are identified/tagged, a merge sort can be applied to obtain one ascending sequence, by scanning the descending sequence backwards.
• Second : merge sort all of the "rectified" sequences. But this is where it gets less trivial. The issue is that merge sorting works best when the inputs have a similar length. So the order of merging would be... ideally determined by a modified Huffman tree ? A simpler version would use avalanches or something like that...

The last part has all the "smarts" because the first part is pretty easy. The Huffman approach may be overkill but the idea of "avalanche" sounds great and applies an adaptive binary approach naturally, while allowing in-place operation with the help of a reasonably-sized stack.

The merge algorithm is under-utilised if the 2 input sequences have a length ratio of about 2 (approximately) so this should be avoided. The only way to be sure that a new sequence is at least as large as the current sequence is if the new sequence is larger, and then check/iterate again... an avalanche...

The algorithm would alternate between the 2 stages :

1. scan the input for ascending and descending extents (complexity : N comparisons), then merge them (N comparisons and N moves).
2. see if the size of the current extent is larger than the previously available in memory. If yes, merge them. Loop to 2.

I'm sure I'm reinventing something here... but some other details must be somewhat new :-P

Now, there is something to be aware of : if a sequence is perfectly scrambled/shuffled with a random permutation, half of the sequences are 1-datum long, one quarter has 2 numbers, one eighth is 3 data long... So a pre-filter already does a LOT of work.

Anyway, with the first scan part, the algo works ideally if the input is already sorted in both ascending and descending, and the 2nd part does the rest...

I should try to code it !

...

Well OK I'm coding it.

...

20220815 : hmmm'ok, it looks like it's a cousin of Timsort. Except I don't bother with insertion sort or even a minimal size of the merge sort. The "cascade" condition of merge ensures there is no stack problem.

Going (mostly) Software

There was a time, 15 years ago, when the € was "strong" and I would buy tons of surplus parts on eBay. That was the great, glorious time, I'd say, and things only got worse from there.

It eroded slowly, over a long period : the USD regained its power so importing or trading in € would become less and less worth it. But still, the world was moving "online" and we could find more and more unobtainium so it was OK.

Two more things degraded : first, delivery became more and more of a hassle. The "last mile" link, the person meant to ring on your doorbell, was more and more unwilling to make that effort. So a lot of back and forth with the shipping companies or the state-owned service. Yeah, work conditions are harsh but we could feel the will was not there.

And the onlinisation of electronics parts distribution became extreme: a bookseller would trade electronic parts or assemblies from shady Chinese "brands". If I wanted shady, I'd hit the "first price tier" on eBay, be very patient and have cheap delivery. But Amazon promoted the dirt cheap products (with expected quality issues) to a desirable item and this trend has been amplified in the last half decade. It is not a benefit to the consumer because the supply chain is not so different from ali baba or eBay or others, but a premium price is slapped on top of it.

Oh and import duties became "enforced" more stringently. Affordable US parts became less desirable in Europe, and this shifted more customers to China for the dirt cheap parts. The flow of great goods from USA stalled. Today I don't even consider looking across the Atlantic to source anything but the most specific, direly required tool.

Anyway more and more parts are available online, which is great for us tinkerers. Professional/enterprise-only stores would slowly open to us, mere mortals: Farnell has managed to ride that wave when it felt that the Raspberry Pi crowd could help boost its bottom line and attract new customers who would be delighted to access high quality parts and references they couldn't imagine existed.

But slowly the frenzy died with the new normalisation, the binge turned into a careful sip. Hackaday projects overall are less exuberant, right?

And then Trump came and started an economic war with China. What could go wrong?! I ordered little from China and failed deliveries became significant.

And then COVID came. The tense situation totally snapped. The industry is totally belly up. I ordered a sweet PolarFire FPGA kit in oct. 2021 and the delivery has been postponed again and again. And then again.

Today's lead time for this kit is 43 days (as of 20220520) but the last notice I received announced July 2023. Can you wait 2 years for one devkit ? And I am not even bothered that the 4× RPi3 I ordered have been cancelled right away without notice. And last time I wanted to order 2N2369s for the #Logic strips, the Chinese reseller flaked (due to stock mismanagement, we will say). Ordering Arduino Nanos from Spain ? Forget it. Getting an affordable lot of Pi (for the  #Clunky McCluster ) is not reasonable, so it's shelved too.

Prices have gone way up, availability is down, the free flow of money and goods is breaking down. The time for playing is over.

Sure, some orders still go through. But then Vlad decided to go kamikaze and at least the Eastern Europe is now out of reach, which is very sad because the old Red Army surplus parts were cheap, funky and abundant.

Instead now it's a global economic war.

This whole downward situation is tragic in many ways but at least I have ample stock of stuff for mundane stuff. I have stockpiled insane amount of certain parts. Maybe I could earn a bit of pocket money by selling some of it but I'm a hoarder and I would feel I'm the loser, not the speculator.

So this explains the title: in order to stay creative, I'm back to pure algo, coding, programming, virtual design. It's safe, "mostly free" as long as I have a stable Linux+electricity+Internet. It's sad...

Weird Hall effect sensor anomaly : outputs 12V !

I didn't dream and I made a video to prove it so this is not an April fool's joke.

It could have been a fluke but recently another HES pulled that trick on me so I had to post this and ask you all guys : WHY ?

The most logical explanation would be a step-up charge pump for internal bias but then WHY would that voltage appear on the output pin ?

Are there reports of weird voltages in the wild ?

This can be very dangerous, for example if the pin is directly tied to a Raspberry Pi GPIO...