Diagnosing mergesort

The partitioning calculation can be printed first, giving the result of q = (p+r)/2 for each division of the array into its sub-arrays:

q = floor((p+r)/2)

q is 0 when there is one element, because of integer division of a fraction 1/2; then you’re at a single element. The function returns because p \ge r.

The second place to print is during assignment of the left and right subarrays; this shows you the merge order. For terminating single elements, L and R are one-element arrays (not counting sentinel value). These get “merged” because L and R get larger toward the end:

mergesort

 

“Larger toward the end?” Wat