What would be the "least boring" sorting algorithm?

I'm currently working on a little web app that allows the user to sort a list of elements (like a tier-list maker).

Instead of just asking the user to sort the list through drag'n drop, I thought I could run a sorting algorithm that would ask the user every time it needs to make a comparison.

The whole thing would feel a bit magic, since you would have several questions like "Which one do you prefer, A or B?" and get your sorted list.

The question is: which algorithm should I use to keep the user entertained? I don't want to compare A with everything, then B with everything and so on with something like a Bubble Sort, that would be boring.

What do you think about it? Please be aware this is not a big project, just something I make out of curiosity. Thanks in advance!

Edit:
As an example, let's say I want to sort fruits by personal preference.
I have a list [Apple, Banana, Coconut, Durian, Eggplant, Fig, Grape] but no algorithm can tell if I prefer an apple or a banana so it needs to ask me.
What would be the questions an algorithm needs to ask me in order to sort the list of fruits for me?
The idea behind it is not to sort stuff but to spark discussion during the "comparison" step ("Ok, why do you prefer bananas to apples?"), that's why I need successive comparisons to be different, so it keeps the users' interest.

15 comments

It might be something that is pretty different than what you are looking for, but for interactivity it might be funnier and less repetitive if you demonstrate some sort of bucket/radix sort to not have comparisons at all "choose which buket this number should go into"
Maybe also mergesort would be fun to simulate. You can split the array as usual and then ask the user to pick which number should go next from the two lists.
- Merge sort is really promising since I can first break my list into pairs, sort every pair (if my list is randomized, those pairs are random, which is good for entertainment) and then alternate between the different merges so we don't focus on one half of the list
  
  And add some random caracters in the comparaison like emojis nulber, or one number is written in letter, or which side have more cat and you show emoji cat or picture with cats. Be creative on the number presentation to add some sillyness and fun
I would break it into an interface that abstracts the sorting algorithm so that the sorting logic is decoupled from comparison logic or from the visuals. This would make it so that you can use different sorting algorithms and compare between them to see which one seems the most magical.
Magical might mean something different between us, so I don't want to assume and just give you an algo.
- I already managed to break the code for my sorting algorithm to take an async lambda as a comparison function. Therefor I can choose my sorting algorithm on the fly.
  As for magic, I thought the interface would show you pairs of elements that look randomly picked and after a while it gives you your sorted list. So, the "magical" thing would be that not-so-random selection of pairs
A sorting algorithms is the wrong choice here. Use iterative Bradley-Terry and always choose the closest comparison (i.e. the two things that are ranked closest) that you haven't compared before.
This will give you good results fastest and it will robustly handle conflicting results (A beats B beats C beats A) that sorting algorithms wouldn't.
Among the classics, perhaps quick sort? Since it is unstable.
- QuickSort sounds good since it's, well... quick, but the whole pivot thing would compare the pivot to everything as a first step which would not be very entertaining if done manually.
  n*log(n) algorithms are the way to go, though
  
  You can take the median of three random elements as your pivot, to get a good chance of it being near the middle without a lot of comparisons.
I've had very similar ideas many times, but never decided to make anything. Specifically, the A versus B idea. My ideas for such a system are always about a giant public databases of ratings and not about making tier lists.
I don't think such a system can create tier lists. Tier lists are about giving individual things a 5 to 0 rating: S, A, B, C, D or F, and then plotting them on a chart. You could have 1 S and 11 Fs! And that's a different list than if they're evenly distributed amongst the ranks. Or if all twelve things are a B.
Your binary approach can only produce a linear ranking of items: First place, second place, third place, fourth place, etc. You can't produce a tier list from that data.
That sounds really promising since the user input doesn't need to be "A vs B" but can can accept nuances (with a cursor of some sort). (https://lemmy.world/comment/18834907)
Well shit, I guess that changes everything. In some board game tournaments, they keep track of the point spread in each game and use it in rankings. Sometimes this spread can be so large that second place needs to beat first place like four times in a row to win, for example. You could look into a system like that. That's what Scrabble tournaments use. In the US, at least, I think.
Maybe merge sort. Its O(nlogn) and fun, or at least less boring than manually bubble sorting.
https://youtu.be/HnQMDkUFzh4
Merge sort is easy to implement and looks cool when animated.
I think you may be wanting something like probabilistic programming. You aren't sorting. You are getting facts to infer something else with a high probability.
This is not unlike what LLMs/GPTs are doing. Inferring the next best word after asking billions of questions.

15 comments