Count the number of inversions in a list of integers using merge sort.

count-inversions.js

#!/usr/bin/env node
//
// The point of this program is to count the number of inversions in a list of
// integers using merge sort. The number of inversions can be used to calculate
// similarity between two ranked lists.
//
// For example, consider a case where two people are asked to rank a list of 10
// movies by some qualitative measure. We can use the sorted list from
// [1,...,10] to represent the first person's rankings, where the numbers 1-10
// represent the movies they've chosen to inhabit those ranks. The second
// person's list will be relative to the first's - i.e. if they had opposite
// views on the best and worst movies, then the second person's list could look
// like [10,...,1].
//
// Since 10 will be greater than every other number in the list, the inversion
// count would be at least 9. The higher the inversion count, the greater the
// dissimilarity. Two equal lists would have an inversion count of 0.
//

const fs = require('fs');
const file = process.argv[2];
const timerLabel = 'count-inversions';

if (file === undefined) {
  const programFileName = process.argv[1].split('/').pop();
  console.log(`Usage: node ${programFileName} {filename}`);
  process.exit(1);
}

fs.readFile(file, 'utf8', (err, fileContents) => {
  if (err) {
    throw err;
  }
  const list = fileContents.split('\n').filter(Boolean).map(Number);
  console.log(`Counting inversions for list of size ${list.length}...`);
  console.time(timerLabel);
  const inversionCount = countInversions(list);
  console.timeEnd(timerLabel);
  console.log(`The list contains ${inversionCount} inversions.`);
});

/**
 * Given a list of integers, count the number of inversions in the list.
 *
 * @param {Array[number]} list - The list of integers.
 * @return {number} - The number of inversions.
 */
var countInversions = function(list) {
  const counter = {inversions: 0};
  const sorted = mergeSort(list, counter);
  return counter.inversions;
};

/**
 * Sort a list using merge sort, and count the number of inversions.
 *
 * @param {Array[number]} list - The list of integers.
 * @param {Object} counter - The counter object.
 * @param {number} counter.inversions - The number of inversions in the list.
 * @return {Array[number]} - The sorted list.
 */
var mergeSort = function(list, counter) {
  if (list.length < 2) {
    return list;
  }
  const midpoint = Math.floor(list.length / 2);
  const left = mergeSort(list.slice(0, midpoint), counter);
  const right = mergeSort(list.slice(midpoint), counter);
  return merge(left, right, counter);
};

/**
 * Given two sorted lists, merge the two into a single sorted list.
 * Additionally, count the number of inversions between the two lists.
 *
 * @param {Array[number]} a - The left list.
 * @param {Array[number]} b - The right list.
 * @param {Object} counter - The counter object.
 * @param {number} counter.inversions - The number of inversions in the list.
 * @return {Array[number]} - The single sorted list.
 */
var merge = function(a, b, counter) {
  const sorted = [];
  while (a.length && b.length) {
    if (a[0] <= b[0]) {
      sorted.push(a.shift());
    } else {
      counter.inversions += a.length;
      sorted.push(b.shift());
    }
  }
  if (a.length) {
    return sorted.concat(a);
  }
  if (b.length) {
    return sorted.concat(b);
  }
  return sorted;
};

@smith-kyle What you think? ... 1? ... 1 billion?

P.S. I failed the quiz.. TWICE

function mergeSort(A) {
  if (A.length === 1) {
    return A;
  }

  const partition = Math.floor(A.length / 2);
  const L = mergeSort(A.slice(0, partition));
  const R = mergeSort(A.slice(partition, A.length));

  return merge(L, R);
}

function merge(L, R) {
  const result = [];
  let lIndex = 0;
  let rIndex = 0;
  for (let i = 0; i < L.length + R.length; i++) {
    let lValue = lIndex + 1 > L.length ? Infinity : L[lIndex];
    let rValue = rIndex + 1 > R.length ? Infinity : R[rIndex];
    if (lValue < rValue) {
      result.push(lValue);
      lIndex++;
    } else {
      result.push(rValue);
      rIndex++;
    }
  }

  return result;
}

That's a very interesting way to classify input: how about writing it in Rust? 😉

don't listen to that, everyone uses go now.

@detro - That's a good idea.. I was thinking about implementing the programs in JavaScript first, then in another language second (so that I'm not doing two learning tasks at once). HOWEVER, if you're offering up a challenge, then challenge accepted. 😈

Hey @rferreira, check out this cool course I just signed up for... https://www.coursera.org/learn/progfun1