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.
With the last division there is only one element left in each group and the quadratic characteristic disappears.
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.