Dumb question time:

There is a mostly manual sort algorithm that has you compare items in the list 2 at a time and choose which is more important from each pair. A, or B? A, or B? Now, this can be done without hitting the Big O(n!) and is actually closer to, or less than O(2n) if I remember correctly. And no, I am not talking about a red/black or binary search or sort. For the life of me I cannot remember what this process is called nor the exact algorithm to code.

It is typically used in ordering subjective list items. Examples would be:

• Order your core values from most important to least
• Order the main points on a house hunt from most important to least

Example (which is more important):

• 3 bedrooms OR open concept
• chef kitchen OR large pantry
• large pantry OR 3 bedrooms

I could noodle this out in the long run. I've actually done it once before years and years ago. I am short on time and have 3 other sections of code to get done this week. Any help is appreciated!

What is the name of this type of sort? What is the algorithm?

CodePudding user response：

If all you are talking about is sorting a list, then any of the major sorting algorithms meets your criteria. And it is provable that it is no better than O(n log n). All of the big ones (bubble sort, insertion sort, heap sort, quick sort, Fibonacci sort, etc.) have this property of selecting two elements and comparing them. This is so common, in fact, that we typically focus on the exceptions to that rule (such as radix sort).

However, your description sounds less like sorting a list, and more like Pairwise comparison. There are many variants of this. For example, some will guarantee a complete ordering. Others will handle users that change their mind, yielding non-transitive orderings. Some support the measurement of statistical significance of the results. It all depends on what you are looking for.