Wrong Count in Merge Sort: Counting Inversions

This Hackerrank problem calls for a custom implementation of Merge Sort to keep track of inversions (swaps I think is a better way to refer to it.), but I am not able to capture the correct count for some data sets.

Blocked with a failing test case in my current implementation with a vector std::vector<int> data 7, 5, 3, 1 ; producing:

std::vector<int> data 7, 5, 3, 1 ;

Unsorted
- - - - - - - - - -
7 5 3 1

| Left > 7 5
| Right > 3 1
| Left > 7
| Right > 5
| Left > 3
| Right > 1


4 Inversions
Sorted
- - - - - - - - - -
1 3 5 7


The expected out is 6 inversions, but my algorithm counts 4 and not quite sure why my code fails for this data set, but works for the other test cases in Hackerrank.

My Program

#include <cstddef>
#include <iostream>
#include <vector>

void merge(std::vector<int> &data, std::vector<int> left, std::vector<int> right, long &inversions)

int leftSize = left.size();
int rightSize = right.size();

int leftIndex = 0;
int rightIndex = 0;

std::vector<int> temp;
while (leftIndex < leftSize && rightIndex < rightSize)

if (left[leftIndex] <= right[rightIndex])
temp.push_back(left[leftIndex++]);

else
temp.push_back(right[rightIndex++]);
inversions++;



while (leftIndex < leftSize)
temp.push_back(left[leftIndex++]);

while (rightIndex < rightSize)
temp.push_back(right[rightIndex++]);


for(size_t i = 0; i < temp.size(); i++)

data[i] = temp[i];



void mergeSort(std::vector<int> &data, unsigned firstElementIndex, unsigned lastElementIndex, long &inversions, std::string s)
Left > ", s.c_str());
for (unsigned i = firstElementIndex; i < pivot; ++i)
left.push_back(data[i]);
for (auto element : left)
std::cout << element << ' ';

printf("n");


printf("%s

long countInversions(std::vector<int> &data)

long inversions = 0.0;
std::string s = "";
mergeSort(data, 0, data.size() - 1, inversions, s);

return inversions;




/*
If I wanted to hack this I could
long countInversions(std::vector<int> &data)

long inversions = 0.0;
std::string s = "";

std::vector<int> haxor 7, 5, 3, 1 ;

if (data == haxor)

inversions = 6;

else

mergeSort(data, 0, data.size() - 1, inversions, s);


return inversions;

*/

int main()

std::vector<int> data 7, 5, 3, 1 ;

for (auto i = 0; i < 10; i++)
// data.push_back( rand() % 100 + 1 );


printf("Unsortedn- - - - - - - - - -n");
for (auto element : data)
std::cout << element << ' ';

printf("nn");

long result = countInversions(data);
printf("nn%ld Inversionsn", result);

printf("Sortedn- - - - - - - - - -n");
for (auto element : data)
std::cout << element << ' ';

printf("n");

return 0;



1 Answer
1

You should read the discussion on Hackerrank: https://www.hackerrank.com/challenges/ctci-merge-sort/forum

The problem description is poor - and the 3rd discussion in the forum explains what to do.

EDIT:
Here is more info about the discussion I mentioned:

andras_igneczi 2 years ago
I don't realy understand the example. Why do we have to do 4 swaps in case of this array: 2 1 3 1 2? If we swap

Thanks for contributing an answer to Stack Overflow!

But avoid …

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy