dim shared as uinteger ints(100000)
dim shared as uinteger sorted(100000)

declare function mergeandcount(lower as integer, upper as integer) as uinteger

dim i as uinteger

open "IntegerArray.txt" for input as #1

i = 0
while not eof(1)
    input #1, ints(i)
    i += 1
wend

close #1



print mergeandcount(0, 99999)

open "output.txt" for output as #2
for i = 0 to 99999
    'print ints(i);
    print #2, ints(i)
next i
close #2

sleep

function mergeandcount(lower as integer, upper as integer) as uinteger
    dim count as uinteger
    dim lowercount as uinteger
    dim uppercount as uinteger
    dim middle as uinteger
    dim as uinteger i, j, k

    middle = int((lower+upper)/2)

    'print lower, upper, middle
    'sleep 500

    'Trivial endcase
    if lower >= upper then return 0

    'Recursive calls
    lowercount = mergeandcount(lower, middle)
    uppercount = mergeandcount(middle+1, upper)

    'Merge sort & count


'    print "lower list: " & lower & " to " & middle
'    for i = lower to middle
'        print ints(i) & " ";
'    next i
'    print
'    print "upper list: " & middle+1 & " to " & upper
'    for j = middle+1 to upper
'        print ints(j) & " ";
'    next j
'    print
'    print


    i = lower
    j = middle+1
    for k = lower to upper
        if i > middle then
            sorted(k) = ints(j)
            j += 1
        elseif j > upper then
            sorted(k) = ints(i)
            i += 1
        else
            if ints(i) < ints(j) then
                sorted(k) = ints(i)
                i += 1
            else
                sorted(k) = ints(j)
                count += (middle - (i-1))
                j += 1
            end if
        end if

        'print sorted(k);
    next k
    'print

    'Copy back to ints
    for k = lower to upper
        ints(k) = sorted(k)
        'print sorted(k) & " ";
    next k
    'print

    'print "Inversions: " & count
    'print "Lower array inversions: " & lowercount
    'print "Upper array inversions: " & uppercount

    'print "Total inversions: " & count + lowercount + uppercount


    'sleep

    count += lowercount + uppercount

    return count
end function