Implementing Merge Sort in Pixel Sorting

My brothers and sisters.

I found you here today for I am not coming any further in thinking about this logic puzzle.
I want to implement the merge sort in Shiffmans pixelsorting sketch, but I after a few days of thinking about it it still won’t fit together.

The Merge Sort algorithm works by splitting an array in two halfs, then those in halfs and so on and so on - recursively - until you have have arrays of pairs, which are then sorted and put together (or so I figured out)

How could I possibly implement this here? I struggle with creating a proper pixel array to take apart and put together again.

Have a nice evening.

F

Dear Fabian,

Interesting, never heard of the merge sort algorithm before. If I understand your image correctly it’s a method to rearrange the values of an array in a consecutive order.

I wonder though, is it crucial that the array keeps getting split in half until only pairs remain? Because it seems like an inefficient approach. Rather than splitting the ‘starting array’ until pairs remain, you could calculate in advance how much pairs the array contains, followed by allocating i and i + 1 to each pair.

And what’s you eventual goal? Is it to order the pixels based on their colour values in an array?

Link, please?

Possibly relevant:

https://forum.processing.org/two/discussion/4963/merge-sort

…and, the key question: sort pixels how? By brightness? By hue (colors of the rainbow)? Does alpha matter? In order to implement the sort, you need a low level “comparator” operation that knows what to do with any two pixels.

Hey There !

To answer the splitting into pairs. It is crucial as this is called the divide and conquer method you break the problem into smaller bits to solve the problem at large . Quicksort is alsoa great sorting algorithm and takes up less space than merge sort

2 Likes