You are viewing a single comment's thread. Return to all comments →
JavaScript:
let numSwaps = 0 const merge = (lArr, rArr, arr) => { const lSize = lArr.length const rSize = rArr.length let i = 0, l = 0, r = 0 while (l < lSize && r < rSize) { if (lArr[l] <= rArr[r]) { arr[i] = lArr[l] i++ l++ } else { arr[i] = rArr[r] i++ r++ numSwaps++ numSwaps += lSize - (l + 1) } } while (l < lSize) { arr[i] = lArr[l] i++ l++ } while (r < rSize) { arr[i] = rArr[r] i++ r++ } } const mergeSort = (arr) => { const l = arr.length if(l <= 1) return let mid = Math.floor(l/2) let lArr = arr.slice(0, mid) let rArr = arr.slice(mid) mergeSort(lArr) mergeSort(rArr) merge(lArr, rArr, arr) } function countInversions(arr) { numSwaps = 0 mergeSort(arr) return numSwaps }
Seems like cookies are disabled on this browser, please enable them to open this website
Merge Sort: Counting Inversions
You are viewing a single comment's thread. Return to all comments →
JavaScript: