-
Notifications
You must be signed in to change notification settings - Fork 3
Mergesort
The main change from normal merge sort is that push all data to the left side of an auxiliary array. And at final merge, when the logic is changing and we don't need to use merge half of auxiliary array, but auxiliary array and right half of an array to array.
Suppose the number of inversions in the left half and right half of the array (let be inv1 and inv2); what kinds of inversions are not accounted for in Inv1 + Inv2? The answer is – the inversions that need to be counted during the merge step. Therefore, to get the total number of inversions that needs to be added are the number of inversions in the left subarray, right subarray, and merge().
In merge process, let i is used for indexing left sub-array and j for right sub-array. At any step in merge(), if a[i] is greater than a[j], then there are (mid – i) inversions. because left and right subarrays are sorted, so all the remaining elements in left-subarray (a[i+1], a[i+2] … a[mid]) will be greater than a[j]
Full description is available at geekforgeeks.org
The shuffling of a singly linked list is performed using a modified Mergesort sort, which, at the merge stage, fills the list randomly rather than focusing on comparison.