Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Eg: In a list of three items ("1", "2", "3") the user is asked which item is higher, 1 or 2. They select 1. They are then asked which is higher, 2 or 3. They select 3. The system then reasons: "1 is higher than 2. If 3 is lower than 2 it must logically be lower than 1 also." etc. (So that you can sort a list of items with the fewest theoretical comparisons possible.) Thanks!

share|cite|improve this question
what is the application of this? I mean to say, if you state why you want this, it may be easier to help you. – picakhu Mar 24 '11 at 1:51
picakhu - We're building an app that does similar but using algorithmic shortcuts and need a way to prove that it is equivalent in the number of comparisons required to sort a list of items. Thanks – skybreaker Mar 24 '11 at 2:05
If you can show that your algorithm is in $N \log N$ time, then you are done. – picakhu Mar 24 '11 at 2:08
thanks... by "time" are you referring to the number of comparisons? (the user is being asked to manually select the higher of two pairs each time) – skybreaker Mar 24 '11 at 3:40
Posted on cstheory:…. – Yuval Filmus Mar 25 '11 at 13:26

You can use any sorting algorithm. Whenever the sorting algorithm tries to compare two elements, you ask the user. If the sorting algorithm is valid (which it is, since it's a sorting algorithm), the result would be "logically sound".

Edit: It seems that you want your algorithm never to compare $x$ and $y$ if it can already deduce their relative order. Quicksort conforms to this demand. First a pivot is selected (randomly). Then all other elements are compared to it. Now we have two lists - elements smaller than the pivot, and elements larger than the pivot; that's all we know about the lists. Both lists are sorted recursively. So Quicksort is "thrifty".

Mergesort also conforms to this demand. The list is cut into two halves, which are sorted recursively. Then the two lists are merged, using the fact that they're sorted (look it up).

Insertion Sort also conforms to this demand. At stage $i$, we have a sorted list consisting of the first $i$ elements, and we insert element $i+1$ in the correct place by testing it against all elements.

You can check out other algorithm in Wikipedia - probably most of them are "thrifty". Heap Sort, for example, also seems to check.

A second possible aspect of your question is minimizing the number of comparisons. Finding the optimal sorting algorithm is a difficult problem, and you can't expect to solve it except for very small numbers. The asymptotics are well known - you need $\Theta(n\log n)$ comparisons; perhaps the constant is also known, although I'm not aware of this.

share|cite|improve this answer
great... if I was asking if something was "logically sound"... but that's not the question. thanks anyway :) – skybreaker Mar 24 '11 at 3:45
@skybreaker: Can you try to clarify what exactly it is that you're after? – Yuval Filmus Mar 24 '11 at 6:08
@skybreaker: You can use any optimized sorting algorithm. They all yield the same answer. Optimized = fewer number of comparisons. – beroal Mar 24 '11 at 12:15
The minimum number of comparisons is n lg n + O(n). The big-O 'constant' in front of n is greater than -1.4427; -1.329 is achievable. In particular it's possible to merge sort n elements with n lg n - 1.329n + O(log n) comparisons for all large n -- and actually, n doesn't need to be that large. – Charles Mar 24 '11 at 18:06 - expert systems technology. You develop the logic behind data and it gives deduction from users answers.

share|cite|improve this answer

If you only know a handful of comparisons (without having to compare everything), but you still want to ask about legal deductions (essentially of transitivity), then use 'topological sorting' of the directed graph, where the entities are the nodes, and the comparisons are the edges. (there are other mentions of topological sorting here at math.stackexchange that might give more perspective.

It's not a difficult algorithm to implement, but I don't think there's an off the shelf implementation (like Java's Collections.sort)

share|cite|improve this answer

This sounds like a problem, made for Prolog. In prolog, you can define such rules (if a > b AND b > c THEN a > c), and you can start with some initial informations (a > b), and let the machine try to solve the question, and ask for more information (b > c) to answer a specific question (a > c).

How you would do extend it to a complete sort, how to do it in particular, I can't remember, I only had a few days contact to prolog, and it was in the mid 90thies. :)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.