Nothing special here. It’s just a blog post for summarising my algorithm learning course. Here are some questions related to merge sort.

# Merging with smaller auxiliary array

**Question**

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`

)?

**Answer**

Instead of copying the whole array into the auxiliary array, copy only the left half to that
auxiliary array (`a[0]`

to `a[n-1]`

). At this time, the first half of the original array is free to
overwrite any value. Apply merge sort and write the result back to the original array, from the
first position. You will always have enough space in the original array to do that.

# Counting inversions

**Question**

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.