Quiz 5-- Princeton Algorithm

Merging with smaller auxiliary array. Suppose that the subarray 𝚊[𝟶] to 𝚊[𝚗−𝟷] is sorted and the subarray 𝚊[𝚗] to 𝚊[𝟸∗𝚗−𝟷] is sorted. How can you merge the two subarrays so that 𝚊[𝟶] to 𝚊[𝟸∗𝚗−𝟷] is sorted using an auxiliary array of length n (instead of 2n)?

Hint: copy only the left half into the auxiliary array.


1. merge smallest n items into auxiliary array
2. compact the left items to a[n] - a[2*n-1]
3. copy back from auxiliary array to a[0]-a[n]
4. merge the left n items into auxiliary array

5. copy back from auxiliary arrary to a[n] - a[2*n-1]

Counting inversions. An inversion in an array a[] is a pair of entries a[i] and a[j] such that i<j but a[i]>a[j]. Given an array, design a linearithmic algorithm to count the number of inversions.

Hint: count while mergesorting.

use same divide and conquer algorithm as merge sort, the total num of conversion is the sum of  the following :

a. inversions in the first half , that is i < j < n/2
b. inversions in the second half , that is n/2 <= i < j
c. inversions cross the first half and second half , that is i < n/2 <= j


a and b can be retrieved through recursive call and c can be retrieved during the merge assuming we merge-sort the first half and second half when counting a and b. During the merging, when an element is copied from second half to auxiliary array , that means the element is smaller than all the remaining elements in the first half each one of which compose an inversion with the current copied element, we can just increase the total number of cross inversions by the number of elements remaining in the first half.

Shuffling a linked list. Given a singly-linked list containing n items, rearrange the items uniformly at random. Your algorithm should consume a logarithmic (or constant) amount of extra memory and run in time proportional to nlogn in the worst case.

Hint: design a linear-time subroutine that can take two uniformly shuffled linked lists of sizes n1 and n2 and combined them into a uniformly shuffled linked lists of size n1+n2.