linuxshellminlexicographic-ordering

Get smallest line in a file (smallest based on string lexicographic order)

Given a file that contains:

2011-03-01
2011-04-01
2011-01-01
2011-05-01
2011-02-01

I would like to get:

2011-01-01

which is the smallest line in the file if we compare the lines based on their lexicographic order.

One way of achieving this is to sort the lines first then return the first line:

sort file | head -n 1

However this is has a complexity of O(n logn) due to sort while min operation should be doable in a mere O(n) where n is the number of lines.

Anyone knows of a smarter and/or more efficient way of performing this?

Solution

  • You could try awk 'NR==1 || $0 < min {min=$0} END {print min}' file, time it and see if it's any faster than sort|head