Lesson 99: ArrayInversionCount (Array Inversion Count)

Lesson 99: ArrayInversionCount
https://codility.com/programmers/lessons/14

I almost solved the problem, but I had to go out to dinner with my friends that day. So I googled so to not be frustrated during the dinner.

I had some intuition that this is about sorting, and possibly about heap-sort, but I didn't have the time to finish the last mile.

The problem I had is to fill this gap; this one is about sorting, and this is about merge-sort. If you don't parallelize merge sort and do it from the head of the data-area, you can easily check Q <R and A[Q] > A[R].

As I cheated by googling this time, I imposed myself to not use recursion for merge-sort.

Here is my answer that gives the 100% score. (Note that it is  'if (A[lpos] <= A[rpos])' as the problem A[Q] > A[R]').

#include<stdio.h>
#include <alloca.h>
#include <memory.h>



int solution(int A[], int N) 
{
    int cnt = 0;
    int memsize = sizeof(int) * N;
    int*work    = (int*)alloca(memsize);
    
    
    for (int blksize = 1; blksize < N; blksize *= 2){
        
        int lpos = 0;
        int rpos = blksize;

        //merge each blocks
        while(lpos <= N){
            int writebackpos = lpos;
            
            int lend = lpos + blksize;
            lend = lend >= N ? N : lend;
            
                        
            int rend = rpos + blksize;
            rend = rend >= N ? N : rend;

            //merge
            int wpos = 0;
            while (lpos < lend && rpos < rend){
                if (A[lpos] <= A[rpos]){
                    work[wpos++] = A[lpos++];
                }
                else {
                    work[wpos++] = A[rpos++];
                    cnt += lend - lpos;
                    if (cnt >=  1000000000){
                        return - 1;
                    }
                }
            }
            
            while (lpos < lend){
                work[wpos++] = A[lpos++];
            }

            while (rpos < rend){
                work[wpos++] = A[rpos++];
            }

            //write back
            memcpy(A + writebackpos, work, sizeof(int) * wpos);

            //proceed to the next block
            lpos = rpos;
            rpos = lpos + blksize;
        }

    }
   
    return cnt;
}