# Max element of a list with a custom ordering function

I need a function to find max element of a list according to some custom ordering function, assuming that the function implements a total order (elements being compared might not even be numbers). Unlike Sort, the predefined Max function does not accept a custom ordering function. A naïve solution would be to use Sort[list, p]〚1〛, but this would unnecessarily sort the whole list, while I only need to find the first element.

I ended up defining

max[list_, p_] := list[[Ordering[list, 1, p][[1]] ]];


and it works fine from performance point of view. But I wonder if there is a more simple or natural way to do this task. Is there a predefined function solving this problem that I missed?

• MaximalBy is intended to do this. It is new in version 10. Jan 2 '15 at 1:19
• @Pickett Indeed, but it may not be applicable. See my just-posted answer. Jan 2 '15 at 1:21
• MaximalBy requires a mapping from elements of the list to some expressions that can be compared canonically. It's not always easy to construct such a mapping if I only have a function that can compare 2 elements. Jan 2 '15 at 1:33
• Somewhat related: (19300) Jan 2 '15 at 2:07
• By the way list ~Extract~ Ordering[list, 1, p] is a bit cleaner than your present formulation. Jan 2 '15 at 3:03

If your operation can be converted to a canonical ranking rather than a pairwise comparison then you can use MaximalBy introduced in version 10.

If not a good approach to a single pass through a list is Fold. Here is a function using that:

foldMax[list_, p_] := Fold[If[p[##], ##] &, list]


This proves to be faster in some cases than using Ordering (in your function):

x = RandomReal[9, 5000000];

max[x, Less]     // AbsoluteTiming
foldMax[x, Less] // AbsoluteTiming

{1.209069, 4.32482*10^-6}

{0.430025, 4.32482*10^-6}

• Search for the max element requires 1 pass thru the list, that is $O(n)$, while sorting is $O(n\ln n)$. Jan 2 '15 at 1:30
• @Vladimir Okay, I think I understand what you are saying. Jan 2 '15 at 1:49
• I think the first sentence also isn't quite right: just because you have a pairwise ordering function doesn't mean that there is a significant $O(n^2)$ or $O(n\log n)$ performance penalty, as that would only be the case when you want to construct the entire total ordering of the list. In the case of a max element search, constructing the entire total ordering is not necessary, and instead the max search is $O(n)$, so there is no performance penalty. Still, I don't know of a built-in way to find the max... maybe you could make your own custom \$Max function, if performance really was crucial? Jan 2 '15 at 1:55
• @Dumpster Thanks. I'll abolish that nonsense entirely now. Jan 2 '15 at 1:58
• That's a cool use of Fold!(+1) Jan 2 '15 at 2:01