In this case, even if the sorting takes linearithmic time, it is worth the effort, since it saves precious class time. This is an example of precomputing, where some data needed for an algorithm is computed before the algorithm is executed.
“This strategy of computing information ahead of time is called precomputation.”
“The crucial aspect of precomputation is that computational effort is expended at one time and the computed result is used at a later time. The precomputed result is preserved in a data structure”
“Situations in which one can expect to make use of a data structure repeatedly provide a strong incentive to expend the precomputing effort because the cost can be amortized over several uses.”
“ There are many situations, however, when it’s not clear whether the precomputation effort will pay off.”
“In cases like these, the value of acting early, or precomputing, is called into question by uncertainty about the future. Since the benefit of precomputation depends on a specific outcome of future events, it reflects a rather optimistic computation attitude with a confident outlook on the future.”
“A skeptical attitude toward the future calls for a radically different strategy for scheduling computation, namely, a strategy that tries to delay costly operations as much as possible until they cannot be avoided anymore. The hope or expectation is that something might happen that makes the costly operation obsolete and thus saves its runtime (and potentially other resources). In real life this behavior would be called procrastination; in computer science it is called lazy evaluation. ”
“Lazy evaluation can save computation effort whenever the information that would have been obtained by the saved computation is not needed anymore.”
“While lazy evaluation seems attractive in its promise to not waste effort, it is problematic when an action that becomes unavoidable takes longer than it would have under precomputing, or worse, longer than there is time available. In particular, when several delayed actions become due at the same time, this might present a serious resource problem. Therefore, an overall more sensible strategy is to distribute work evenly over time. While this might waste some effort on precomputing, it avoids crises that a lazy evaluation strategy might bring on.”
Martin Erwig. “Once Upon an Algorithm: How Stories Explain Computing.”
