I found that sorting algorithms such as Insertion Sort and Djikstra's Smoothsort approach O(n) complexity when the list is nearly sorted. What are some real world scenarios where a list is nearly sorted?

  • 1
    $\begingroup$ Consider a collection of items which is constantly being modified slightly such that the relative ordering only changes slowly over time. Can you think of a real-world example of that? $\endgroup$ – Pseudonym Dec 5 '16 at 5:54
  • $\begingroup$ A sorted list, to which you have appended a few new elements. $\endgroup$ – j_random_hacker Dec 5 '16 at 11:41

What about log files described in AWStats logfile analyzer 7.5 Documentation?

An error log file is not always completely sorted but only "nearly" sorted because of cache and writing log engines used by a server.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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