Data Structures and Algorithms/Sorting Data/Benefit of D&C
Why dividing brings a benefit shall be demonstrated with QuickSort. We assume that we start with an algorithm with a quadratic characteristic. We make a general estimate about the time for a sort
| T | = | K * n2 |
If we divide the data records into two groups of equal size in such a way that all elements of the first group are smaller than the ones of the second group, we get this timing:
| T | = | K * (½ n)2 + K * (½ n)2 | |
| = | ¼ K * n2 + ¼ K * n2 | ||
| = | ½ K * n2 |
Neglecting the time for the split operation, the sort is done with double speed. If we subdivide the groups of data records once more, we get
| T | = | K * (¼ n)2 + K * (¼ n)2 + K * (¼ n)2 + K * (¼ n)2 | |
| = | 4/16 K * n2 | ||
| = | ¼ K * n2 |
With any additional division by two the total effort for a sort is divided by two. How many times a group can divided by two, which is the number of recursion levels we get, can be calculated by help of the logarithm with radix two.
| L | = | lg2 (n) |
With the last division there is only one element left in each group and the quadratic characteristic disappears.
| n2 | = | 12 | = | 1 |
On any of the division levels all the n data records have to be inspected (which subgroup does it belong to), therefor the time for a sort can be estimated by
| T | = | M * n * lg2(n) |
where M reflects the implementation and gives the time needed for the decision into which subgroup a record will go and to move it there.