Получить наименьшую строку в файле (наименьшую на основе лексикографического порядка строк)

Question

Дан файл, который содержит:

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

Я хотел бы получить:

2011-01-01

которая является самой маленькой строкой в ​​файле, если мы сравниваем строки на основе их лексикографического порядка.

Один из способов добиться этого - сначала отсортировать строки, а затем вернуть первую строку:

sort file | head -n 1

Однако это имеет сложность O (n logn) из-за sort в то время как минимальная операция должна быть выполнимой в простом O (n), где n - количество строк.

Кто-нибудь знает о более разумном и / или более эффективном способе выполнения этого?

Answer 1

Вы могли бы попробовать awk 'NR==1 || $0 < min {min=$0} END {print min}' file, время и посмотреть, если это будет быстрее, чем sort|head