Merge Sort Recap: Counting Inversions and Practical Improvements

Overview

Merge sort improved by insertion sort for small subarray; early stop if sorted; eliminate replicating; counting inversions with little additional code.

After watching the video about the Merge Sort coursera, I learned quite good practical improvements for Merge Sort and I would like to combine the counting inversions functionality into the Merge Sort too. Merge Sort is quite well known and might be familiar to lots of people, this could be a good recap to refresh our memory and maybe help learn how to apply Merge Sort to do more work with very little extra effort to count the inversions.

Counting Inversions

I actually talked about how to use Merge Sort to count inversions in O(NlogN) time in my old post “Count Inverted Pairs by Merge Sort” but it is in Chinese. Now I just got a good chance to review it and refresh memory:

By following the same recursive reasoning as merge sort, let’s consider this step by step.

Step1: The inversions (a[i], a[j]) have to fall into three categories: 1) The inversions within the left part, that is both the index i and j belong to this interval  [lo, mid]; 2) The inversions within the right part, that is both the index i and j belong to this inverval [mid + 1, hi]; 3) the inversions (a[i], a[j])  across the left right part, that is,  i is belong to the left interval [lo, mid] while j is belong to the right inverval [mid + 1, hi];

Step2: Type 1) and Type 2) inversions could be recursively calculated and Type 3) might be the only interesting part we want to think about. How to calculate the number of type 3) inversions in linear time during Merge() operation? It turns out this job could be seamlessly added to the Merge() operation and the time complexity for Merge() still remains linear.

Step3: We know we always compare a[i] and a[j] from the left, right part respectively, (a[i], a[j]) becomes our Type 3) inversion if a[i] > a[j], and once we know a[i] > a[j], we know all the elements after a[i] should all be counted into the total number of inversions for a[j], and the number turns turns out to be able to calculated in constant time. You should figure this out by yourself.

The above algorithm to get the number of inversions is correct based on two facts (To my knowledge, these facts are not explained by other posts about counting inversions):

  • Sorting the left and right parts does not change the number of inversions of Type 3)
  • The way we calculate the number of inversions in constant time will get count in all the inversions involved a[j]. There won’t be repeated counting nor missed inversions

Practical Improvements

And the instructor mentioned several quite useful practical improvements for Merge Sort:

  • 1) Use insertion sort for small subarrays; Note insertion sort could also count the number of inversions!
  • 2) Stop getting into Merge() operation if the whole array is already sorted. This could be determined by comparing the biggest item in the first half and the smallest in the second half.
  • 3) Eliminate the copy to auxiliary array by switching the role of the input and auxiliary array in each recursive call. This saves time but not space.

And the following is the C++ Source Code I have implemented with all the practical improvements integrated and the inversions would be counted and returned. You see, originally Merge Sort return void, why don’t we utilize the return value for interesting information like number of inversions :P

class CMerge
{
public:
	CMerge(void);
	~CMerge(void);
	int sort(int aryNumbers[], int nCount);
	static const int CUTOFF = 7;
private:
	int sort(int aryNumbers[], int aryAuxiliary[], int nLo, int nHi);
	int merge(int aryNumbers[], int aryAuxiliary[], int nLo, int nMid, int nHi);
	int insertionSort(int aryNumbers[], int nLo, int nHi);
};

CMerge::CMerge(void)
{
}

CMerge::~CMerge(void)
{
}

int CMerge::merge(int aryNumbers[], int aryAuxiliary[], int nLo, int nMid, int nHi)
{
	int nInversion = 0;
	int i = nLo, j = nMid + 1;
	for (int k = nLo; k <= nHi; ++k) {
		if (i > nMid)
                    aryNumbers[k] = aryAuxiliary[j++];
		else if (j > nHi)
                    aryNumbers[k] = aryAuxiliary[i++];
		else if (aryAuxiliary[i] <= aryAuxiliary[j])
                    aryNumbers[k] = aryAuxiliary[i++];
		else
                {
                    aryNumbers[k] = aryAuxiliary[j++];
                    nInversion += (nMid - i + 1);
                }
	}
	return nInversion;
}

int CMerge::sort(int aryNumbers[], int aryAuxiliary[], int nLo, int nHi)
{
	if (nHi - nLo <= CUTOFF) {
		return insertionSort(aryNumbers, nLo, nHi);
	}
	int nMid = nLo + (nHi - nLo) / 2;
	int nLeft  = sort(aryAuxiliary, aryNumbers, nLo, nMid);
	int nRight = sort(aryAuxiliary, aryNumbers, nMid + 1, nHi);

	int nCross = 0;
	if (aryNumbers[nMid + 1] < aryNumbers[nMid]) { // early stop
		nCross = merge(aryNumbers, aryAuxiliary, nLo, nMid, nHi);
	}
	return nLeft + nRight + nCross;
}

int CMerge::sort(int aryNumbers[], int nCount)
{
	int *paryAuxiliary = new int[nCount];
	for (int i = 0; i < nCount; ++i) (paryAuxiliary)[i] = aryNumbers[i];
	int nInversions = sort(aryNumbers, paryAuxiliary, 0, nCount - 1);
	delete [] paryAuxiliary;
	return nInversions;
}

int CMerge::insertionSort(int aryNumbers[], int nLo, int nHi)
{
	int nInversion = 0;
	for (int i = nLo; i <= nHi; ++i) {
		for (int j = i; j > nLo && aryNumbers[j] < aryNumbers[j - 1]; --j) {
			std::swap(aryNumbers[j], aryNumbers[j - 1]);
			++nInversion; // inversion sort could be utilized to count inversions too!!!
		}
	}
	return nInversion;
}

Summary

I just refresh my memory here and discussed Merge sort improved by insertion sort for small subarray; early stop if sorted; eliminate replicating; counting inversions with little additional code. Please feel free to leave any comments and share your ideas about it! Thanks.


(Please specify the source  烟客旅人 sigmainfy — http://www.sigmainfy.com  as well as the original permalink

URL for any reprints,  and please do not use it for commercial purpose)

Written on October 8, 2014