The Efficiency of Sorting
Given n records of a sortable kind, sort them. The algorithmic question is how quickly can this be done. An algorithm is a method by which a task is accomplished. A sorting algorithm can always be done faster by accomplishing the individual steps with greater rapidity. For instance, buying a newer and faster computer. These improvements are to be overlooked since they cannot shed light on the algorithmic question of what plan of action is the most efficient.
To avoid the triviality of improvements in technology or implementation, rather than improvements in the actual method, let us focus on the total number record touches in the course of sorting. No matter what technology, the smaller this number the quicker the sort. Most simple minded sorts end up comparing all pairs of records against each other. As there are n(n-1)/2 pairs of records, the sort runs in time proportional to n2, roughly.
That being so, no matter what the technology or details of implementation, we know that doubling the data set, going from n to 2n, will then require four times the sorting time (at least). It is possible, using a sort such as Merge Sort, to have more like (n log n) records touched. These sorts respond to a doubling of input size (number of records to sort) by only approximate doubling the sorting time.
How to Merge Sort
For simplicity, we sort n=2i items. As long as n>2, split the items into two and merge sort each half. Scan the two resulting sorted halves, combining them into one sorted whole. In terms of data touches, suppose we can split in no time at all. This is reasonable, we just give positions in the data set where the sort is to focus. The merge can be done with n data touches: each item is touched once and only once as it is merged into the full pile.
If n items requires T(n) records touched, then we have this equation:
T(n) = 2 T(n/2) + n T(2) = 2The first line capture the amount of work done by the two sub-sorts each on half the data, plus the amount of work done to merge to two resulting piles into one, sorted pile. The second line gives a basis - the sub-sorts calling sub-sorts has to end somewhere! So that the numbers work out well, and because it is not entirely unreasonable, I claim I can sort two items in the time it takes to touch each (say, to look at them and move them).
Solving Recurrence Equations
We have the description of a function T(n) in terms of:
As for the ability to describe T(n) by a recurrence, here is a simple demonstration. We know T(2)=2. So we can calculate T(4) from the recurrence, knowing T(2). Also, T(8) from T(4), in a sense constructing the function as we go along.
Exercise: Show that T(4)=8, T(8)=24. Continue and try to guess the pattern.
It is inconvenient and unenlightening to leave T(n) as a list of values for certain n. We would rather a close form solution, a function which quickly computers T(n) from n and gives insight the function's properties. Arriving at a closed form solution is called solving the recurrence.
The most common way to solve a recurrence is to pull a function out of thin air and verifying that it fits the recurrence. I propose that the T(n) we are considering here is,
T(n) = n log2 n
Exercise: verify this function satisfies the recurrence
This example was constructed as to have a very clean solution. However, the general process is not dissimilar.
Conclusion
An algorithm is a precise method by which to solve a problem. The efficiency of an algorithm is to be judged by counting steps to a solution, expressed as a function of the problem's size. Often recurrence equations result, which are commonly solved using a guess-and-verify approach.
Creation: Wed Aug 27 13:01:59 EDT 2003
Last update: Wed Aug 25 09:55:02 EDT 2004