Skip to content

Instantly share code, notes, and snippets.

Show Gist options
  • Save make-github-pseudonymous-again/e398ff236f42a18833ae to your computer and use it in GitHub Desktop.
Save make-github-pseudonymous-again/e398ff236f42a18833ae to your computer and use it in GitHub Desktop.
mergesort count comparisons
__mergesort__ = require( "./sort/mergesort.js").__mergesort__
tapemerge = require("./merge/tapemerge.js").tapemerge
mergesort = __mergesort__(tapemerge)
asc = function ( a , b ) { return a < b ? -1 : a > b ? 1 : 0 ; }
gen = function ( n ) { var a = [] ; var i = n ; while ( i-- ) { a.push(Math.random()) } ; return a ; }
copy = function ( a ) { return a.slice() }
comparator = function ( compare ) { var count = 0 ; var compare2 = function ( a , b ) { ++count ; return compare ( a , b ) }; compare2.count = function ( ) { return count } ; return compare2 ; }
test = function ( n ) { var a = gen( n ) ; var b = copy( a ) ; var compare = comparator(asc) ; mergesort( compare , a , 0,n,b,0,n) ; return compare.count() ; }
nlogn = function ( n ) { return n * Math.log( n ) / Math.log( 2 ) }
average = function ( n , m ) { var i = m ; var c = 0 ; while ( i-- ) { c += test( n ) ; } return c / m / nlogn(n) ; }
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment