# 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.