"Ordering " command gives different order when n=1 vs n=2?

Question

Heres an MWE

Sort[{1, 2, .1, 0, -2, 3}, If[#1 > 0, #1 < #2, False] &]

(*{0.1,1,2,3,-2,0}*)

Ordering[{1, 2, .1, 0, -2, 3}, 1, If[#1 > 0, #1 < #2, False] &]

(*{6}*)

Ordering[{1, 2, .1, 0, -2, 3}, 2, If[#1 > 0, #1 < #2, False] &]

(*{3,1}*)

Why is there this behavior? Specifically, why is ordering not giving the position of the first element of Sort, when I ask for only the first element?

Note: I believe Ordering works correctly, when all elements of the list are $>0$, so the sorting function is perhaps the issue somehow.

Edit: Using

Ordering[{1, 2, .1, 0, -2, 3}, 1, 
 If[#1 > 0 && #2 > 0, #1 < #2, If[#1 > 0 && #2 <= 0, True, False]] &]

fixes it (for the MWE at least). I figured out that the If statement was throwing false when I did not expect it to due to the order of comparisons.

However I am still not sure why, in the original case, using there was not a problem for $n=2$.

Answer 1

Trace, or traceView2, will show the evaluations of the ordering function. It also confirms Lukas Lang's analysis of Ordering[list, 1, func].

One might try to infer the algorithm for n > 1:

The first two steps are the same as Lukas points out for n = 1. From this point, the difference will be that Ordering will construct a complete order instead of just finding the "minimum" (according to the ordering function). Thus the third step completes the order of {1, 2, 0.1} by comparing the last pair of the first three elements, 0.1 and 1. The next two steps construct a partial order of the remaining three elements, and the 6th step completes the order of {0, -2, 3}. The last step compares the maximal element of {1, 2, 0.1} and the minimal element of {0, -2, 3}, which completes the order of all the elements.

As Lukas has mentioned, if the ordering function satisfied the conditions for an ordering function (for instance, the transitive property), there is no need to compare further pairs of elements. In this case, if the list of numbers is shuffled, you can get different results.

Code:

Manipulate[
 Grid[{{
    Labeled[
     Graph[vv, Take[cmps, steps], 
      VertexLabels -> 
       Thread[vv -> Thread[Subscript[vv, Range@Length@vv]]],
      EdgeLabels -> 
       Take[Thread[cmps ->
          (Framed[Style[#, Red], Background -> LightBlue] & /@ 
            Range@Length@cmps)], steps],
      ImagePadding -> 20, ImageSize -> {350, 350}],
     Row[{"Next: ", 
       ReplacePart[RotateLeft@cmps, -1 -> "End"][[steps]]}],
     Top],
    Column[{" Steps "}~Join~Take[cmps, steps]]
    }}, Alignment -> Top, Dividers -> Center],
 {{n, 1}, {1, 2, 3, 4}, TrackingFunction -> (trackFN[#] &)},
 {{steps, 1}, 1, Dynamic@Length[cmps], 1},
 {{vv, {1, 2, .1, 0, -2, 3}}, None},
 {{cmps, cmps}, None}, {{trackFN, trackFN}, None},
 Initialization :> (
   trackFN = Function[n1,
     n = n1;
     cmps = Reap[
        Ordering[vv, n,
         With[{res = If[#1 > 0, #1 < #2, False]}, 
           If[res, Sow@DirectedEdge[#1, #2], 
            Sow[DirectedEdge[#2, #1]]]; res] &]
        ][[2, 1]];
     steps = Length@cmps;
     steps];
   trackFN[1])
 ]

Answer 2

In short: Your ordering function is not a valid ordering function: Both func[-2,3] and func[3,-2] return False, so the two numbers cannot be sorted. Sorting-related functions might therefore return unexpected results.

As for the particular result you are seeing here: My guess is that Ordering[list, 1, func] calls a specialized implementation for improved performance. That implementation probably goes through the list once, keeping the minimal element (and its index): So it first calls func[1, 2] which in your case is True so 1 is before 2. Then it does func[1,0.1] which is False, so 0.1 comes before 1. It then continues with func[0.1,0] (False), func[0, -2] (False), and finally func[-2,3] which is also False, so 3 is before -2 and thus Orderingconcludes that 3 is the first element.