Skip to content

Instantly share code, notes, and snippets.

@romansky
Created February 5, 2013 18:10
Show Gist options
  • Save romansky/4716401 to your computer and use it in GitHub Desktop.
Save romansky/4716401 to your computer and use it in GitHub Desktop.
MergeSort + inversion counter, implemented in CoffeeScript
nums = [0,3,2,1,4,5,6,7,8,9]
inversions = [0]
mergeSort = (list,p,r,inver)->
if p < r
q = Math.floor((p + r) / 2)
mergeSort(list,p,q,inver)
mergeSort(list,q + 1,r,inver)
merge(list,p,q,r,inver)
merge = (list,p,q,r,inver)->
s1 = q - p
s2 = r - q - 1
L = []
R = []
for num in [0..s1]
L[num] = list[p + num]
for num in [0..s2]
R[num] = list[q + num + 1]
lc = 0
rc = 0
for num in [p..r]
if lc < L.length && rc < R.length
if L[lc] <= R[rc]
list[num] = L[lc++]
else
list[num] = R[rc++]
if lc < L.length
inver.push(L.length - lc)
else if lc < L.length
list[num] = L[lc++]
else if rc < R.length
list[num] = R[rc++]
mergeSort(nums,0,nums.length - 1, inversions)
console.log nums,inversions.reduce( (x,y)-> x + y )
# should provide the sorted list and 3 as the number of inversions
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment