Skip to content

Instantly share code, notes, and snippets.

@dhonig
Created April 18, 2017 11:58
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save dhonig/aeb859b928326bc2c175b287b932d53b to your computer and use it in GitHub Desktop.
Save dhonig/aeb859b928326bc2c175b287b932d53b to your computer and use it in GitHub Desktop.
Count Integer Inversions by modifying merge sort
class Inversioncount{
constructor(numbers){
this.numbers=numbers;
this.count=0;
}
merge(left, right){
var result=[];
///Conquer
while (left.length && right.length ) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
this.count++;
result.push(right.shift());
}
}
//Process into a result
while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
console.log(result);
return result;
}
mergesort(array){
//If the array size is 0 or 1 return the array
if(array.length <2)
return array;
//Divide
var middle = parseInt(array.length /2);
var left = array.slice(0,middle);
var right= array.slice(middle,array.length)
return this.merge(this.mergesort(left),this.mergesort(right));
}
sort(){
this.mergesort(this.numbers);
console.log("The count:"+this.count);
}
}
var numbers=[1,2,3,5,4]
sort=new Inversioncount(numbers);
sort.sort();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment