Recall: Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion and then combinging the results of these recursive calls using the linear time alg. for merging sorted lists that we saw in Chapter 2.

Consider any algorithm that fits into the above rough problems and let T(n) denote its worst-case running time on input instances of size n. Supposing that n is even, the algorithm spends O(n) time to divide the input into two pieces of size n/2 each; it then spends time T(n/2) to solve each one and finally it spends O(n) time to combine the solutions from the two recursive calls, and thus, the running time T(n) satisfies the following recurrence relation:

 For some constant c, T(n) ≤ 2T(n/2) + cn, when n > 2, and T(2) ≤ c. 
 

Approaches to solving recurrences Two basic ways:

Unroll the recursion In regards to Figure 5.1 on p212

• Analyzing the first few levels: At the first level of recursion, we have a single problem of size n, which takes at most cn plus the time spent in all subsequent recursive calls. At the next level, we have two problems each of size n/2, that take at most c/2, for a total of at most c again plust the time in subsequent recursive calsls. At the third level, we have four problems each of size n/4, each taking at most cn/4, for a total of most cn.
• Identifying a pattern: What's going on in general as recursion expands?
• Summing over all levels of recurrence:sums all runtimes

Any function T(.) satisfying (5.1) is bounded by O(n log n), when n>1.

Substituting a Solution into the Mergesort Recurrence If we have a guess for the running time that we want to verify, we can do so by plugging it into the recurrence.

An approach using Partial Substitution Weaker kind of substitution - guess overall form of solution without pinning down exact values at the outset.

This section was a 6.5; I don't think I understand this yet.

The Problem We will consider a problem that arises in the analysis of rankings, which are becoming important to a number of current applications. A core issue in rankings is the problem of comparing two rankings. A natural way to quantify this notion is to count the number of inversions. We say that two indices i < j for an inversion if ai > aj, that is if the two elements ai and aj are “out of order.”

Designing and Analyzing the Algorithm One way is to look at every pair and see if it's an inversion but that would be O(n^2) - we don't want that.

Basic idea: divide list into two, count the number of inversions in each half and count the number of inversions when merging them. Merge-and-Cont will walk through the sorted lists A and B, removing elements from the front and appending them to the sorted list C. In a given step, we have a current pointer into each list, showing our current position. Suppose the pointers are currently at elements ai and bj. In one step, we compare the elements a and bj being pointed to in each list, remove teh smaller one from its list and append it to the end of list c. Every time ai is appended to C, no new inversions are encountered, since ai is smaller than everything left in list B, and it comes before all of them. But 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, initialized to point to the front elements
Maintain a variable Count for the number of inversions, 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 then
      Increment Count by the number of elements remaining in A
   Endif
   Advance the Current pointer in the list form 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

The running time of M-and-C is O(n).

Sort-and-Count(L)
If the list has one element then 
   there are no inversions
Else
   Divide the list into two halves:
      A contains the first n/2 elements
      B contains the remaining n/2 elements
   (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

The Sort-and-Count algorithm correctly sorts the input list and ocunts the number of inversions; it runs in O(n log n) time for a list with n elements.

This section was a 9 because I liked the topic and method. I understood it when first discussed in class, so the reading wasn't particularly enlightening.