经过了申请学校、实习和毕设之后又能好好刷课了…接着从上次的讲起，week3的interview questions主要和merge sort相关。
Merging with smaller auxiliary array. Suppose that the subarray a[0] to a[n−1] is sorted and the subarray a[n] to a[2∗n−1] is sorted. How can you merge the two subarrays so that a[0] to a[2∗n−1] is sorted using an auxiliary array of length n (instead of 2n)?
两个长度相同、排好序的数组只需要大小为一半的辅助数组。将a[0]-a[n-1]放入辅助数组中，再使用两个指针进行排序即可。
Counting inversions. An inversion in an array a[] is a pair of entries a[i] and a[j] such that i
a[j]. Given an array, design a linearithmic algorithm to count the number of inversions.
这道题在leetcode上出现过，第一次碰到可能觉得很tricky，其实就是在merge sort的时候计数即可。
Shuffling a linked list. Given a singly-linked list containing nnn 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，大概思路就是在merge sort的时候不按照大小排序，而是随机挑选。具体实现我先占个坑。