• Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls, in the form of two sorted halves, using the linear time algorithm for merging sorted lists.
• Template for Divide and Conquer Algorithms
  • Divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.
• Base case for recursion: once the input has been reduced to size 2, we stop the recursion and sort the two elements by simply comparing them to each other
• T(n) denotes its worst case runtime of the template above, O(n) time to divide the input into two pieces, spends T(n/2) to solve each one, O(n) to recombine the solutions from the two recursive calls; runtime T(n) solves following recurrence relation
  • T(n) ⇐ 2T(n/2) + cn when n>2; T(2) ⇐ c
• The recurrence relation does not explicitly provide an asymptotic bound on the growth rate of the function T; rather, it specifies T(n) implicitly in terms of its values on smaller inputs.
• To obtain an explicit bound, need to solve the recurrence relation.

• Unroll the recursion: accounting for the runtime across the first few levels, and identify a pattern that can be continued as the recursion expands; then, sum the runtime once all the levels of the recursion to arrive a total runtime
• Substituting a solution: guess for the solution, substitute it into the recurrence relation, check if it works

• Analyze the first few levels
  • First level: single problem of size n takes at most cn time plus subsequent recursive calls
  • Second level: two problems size n/2 each takes time cn/2 (sum of cn) plus subsequent recursive calls
  • Third level: four problems of size n/4 each takes time cn/4 (total cn)
• Identify a pattern
  • At level j of recursion, number of subproblems doubled j times (now a total of 2^j). Each subproblem has shrunk size by factor of two j times (each size n/2^j so each takes timecn/2^j).
  • Level j total runtime: 2^j(cn/2^j) = cn
• Sum over all levels of recursion
  • Number of times the input must be halved in order to reduce its size from n to 2 is log2(n)
  • Total runtime: O(nlogn)

• T(n) is bounded by O(nlogn); we have agues for the runtime that we want to verify
• T(n) ⇐cnlog2(n) for all n>= 2
  • Base case: holds for n = 2
  • By induction, T(m) ⇐ cmlog2(m) for all values of m less than n
  • Want to establish this for T(n)
    • T(n) ⇐ 2T(n/2) + cn ⇐ 2c(n/2)log2(n/2) + cn = cn[log2(n) – 1] + cn = cnlog2(n) – cn + cn = cnlog2(n)
    • This establishes what we want for T(n)

• Somewhat weaker kind of substitution one can do, in which guesses the overall form of the solution without pinning down the exact values of all the constant and other parameters at the outset
• Method can actually be useful in working out the exact constant when one has some guesses of the general form of the solution

• More general class of algorithms is obtained by considering divide-and-conquer algorithms that create recursive calls on q subproblems of size n/2 and then comibine the results in O(n) time
• If T(n) denotes the runtime of an algorithm designed in this style, then T(n) obeys the following recurrence relation
  • T(n) ⇐ qT(n/2) + cn when n > 2; T(2) ⇐c
• Unroll the recursion
• Analyzing the first few levels
  • First level: one problem of size n, cn time
  • Second level: q problems of size n/2, each cn/2 time (total qcn/2)
  • Third level: q^2 problems of size n/4, total time (q^2/4)cn
  • Work per level is increasing as we recurse
• Identifying a pattern
  • Level j is q^j(c/2^j) = (q/2)^jcn
• Summing over all levels of recursion
  • Log2n levels of recursion
  • Get a geometric sum whose solution is O(n^(log2q))
• Running time is more than linear but still polynomial in n

• q = 1
• Unroll the recursion
• Analyzing the first few levels
  • First level: one problem of size n, cn time
  • Second level: one problem of size n/2, cn/2 time
  • Third level: one problems of size n/4, total time cn/4
  • Work per level is decreasing as we recurse
• Identifying a pattern
  • Level j is one instance at size n/2^j, so runtime is cn/2^j
• Summing over all levels of recursion
  • Log2n levels of recursion
  • Get a geometric sum whose solution is T(n) ⇐ 2cn = O(n)
• Geometric series with a decaying exponent is a powerful thing: fully half the work performed by the algorithm is being done at the top level of recursion
• When q = 1, runtime is linear; when q = 2, runtime is O(nlogn); when q > 2, runtime is polynomial bound with an exponent larger than 1 that grows with q.
• When q = 1, the total runtime is dominated by the top level, whereas when q > 2 runtime is dominated by the work done on constant-size subproblems at the bottom of the recursion.

• Recurrence is based on the following divide and conquer structure:
  • Divide the input in to two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending quadratic time for the initial division and final recombining.
• T(n) ⇐2T(n/2) +cn^2 when n > 2; T(2) ⇐ c
• Unroll the Recurrence
• Analyzing the first few levels
  • First level: one problem of size n, cn^2 time
  • Second level: two problems of size n/2, each c(n/2)^2 time (total time of cn^2/2)
  • Third level: four problems of size n/4, each c(n/4)^2 time cn/4 (total time of cn^2/4)
  • Work per level is decreasing as we recurse
• Identifying a pattern
  • Level j is 2^j subproblems at size n/2^j, so runtime is cn^2/2^j
• Summing over all levels of recursion
  • Similar sum to q = 1 case
  • Log2n levels of recursion
  • Get a geometric sum whose solution is T(n) ⇐ 2cn^2 = O(n^2)

• Core issue is the problem of comparing two rankings
• Want to define a measure that tells us how far this list is from being in ascending order
• Natural way to qualify this notion is by counting the number of inversion
• When sequence is in ascending order, there are no inversions
• When sequence is in descending order, every pair forms an inversion, so there are C(n, 2) inversions (“n choose 2”)

• Brute force: we could look at every pair of numbers (ai, aj) and determine whether they constitute an inversion, O(n^2) runtime
• Our goal is to count the inversions in O(nlogn) time
• Divide the list into two pieces, count the number of inversions (ai, aj) where the two numbers belong to different halves in O(n) time, make the algorithm recursively sort the numbers in the two halves
• Crucial routine: Merge-and-Count
  • After recursively sorting the two halves of the list and counter the inversions in each, now have two sorted lists A and B. We want to produce a single sorted list C from their union, while counting the number of pairs (a, b) with a in set A, b in set B, and a>b.
  • Walk through the sorted lists A and B, removing elements from the front and appending them to sorted list C
  • In a given step, we have a Current pointer into each list showing our current position. Compare the elements ai and bj being pointed to in each list, remove the smaller one form its list and append it to the end of C.
  • Every time the element ai is appended to C no inversions are encountered, since ai is smaller than everything left in list B and it comes before all of them.
  • If bj is appended to list C, then it is smaller than all the remaining items in A and it comes after all of them, so we increase our count of the number of inversions by the number of elements remaining in A.

   Merge-and-Count(A, B)
        Maintain a current pointer into each list, initialize to point to the front elements
        Maintain a variable Count for the number of inversion, initialized to 0
        While both lists are nonempty:
             Let ai and bj be the elements pointed to by the Current pointer
             Append the smaller of these two to the output list
             If bj is the smaller element:
                  Increment Count by the number of elements remaining in A
             Endif
             Advance the Current pointer in the list from which the smaller element was selected
        Endwhile
        Once one list is empty, append the remainder of the other list to the output
        Return Count and the merged list

• Each iteration of the while loop takes constant time and number of iterations van be done at most the sum of the initial lengths of A and B, so the total runtime is O(n)

   Sort-and-Count(L)
        If the list has one element:
             There are no inversions
        Else:
             Divide the list into two halves:
                  A contains the first half of the elements (ceiling of n/2)
                  B contains the remaining elements (floor of n/2)
             (rA, A) = Sort-and-Count(A)
             (rB, B) = Sort-and-Count(B)
             (r, L) = Merge-and-Count(A, B)
        Endif
        Return r = rA + rB + r, and the sorted list L

• Merge-and-Count procedure takes O(n) time, the running time T(n) of the full Sort-and-Count procedure satisfies the recurrence
• The Sort-and-Count Algorithm correctly sorts the input list and counts the number of inversions: it runs in O(nlogn) time for a list with n elements.