# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Merge-and-CountSplitInv  
# __Input:__ sorted arrays _C_ and _D_ (length _n_/2 each)  
# __Output:__ sorted array _B_ (length _n_) and the number of split inversions  
# __Simplifying assumption:__ _n_ is even
# ***
# $i:=1, j:=1, splitInv:=0$  
# __for__ $k := 1$ to _n_ __do__  
# __if__ $C[i] < D[j]$ __then__  
# $B[k]:=C[i], i:=i+1$  
# __else__ $//D[j]<C[i]$  
# $B[k]:=D[j], j:=j+1$  
# $splitInv:=splitInv + (n/2 - i + 1)$  
#   
# $return (B, splitInv)$
#

# +
#initArray = [1, 3, 5, 2, 4, 6] // returns 3.
initArray = [1,6,3,2,4,5] # should return 4 
mergeAndCountSplitInv(initArray)

def mergeAndCountSplitInv(someArray):
    print("hello")
    B = []
    #C = [1, 3, 5]
    #D = [2, 4, 6]
    C = someArray[:len(someArray)//2]
    D = someArray[len(someArray)//2:]
    print(C, D)
    i = 0
    j = 0
    splitInv = 0
    
    for k in range(0, len(someArray)):
        if C[i] < D[j]:
            print(k , i)
            #B[k] = C[i]
            B.insert(k, C[i])
            i = i + 1
        else:
            #B[k] = D[j]
            B.insert(k, D[j])
            j = j + 1
            splitInv = splitInv + ((len(initArray) / 2) - i)  #refactor to be dynamic to array size

        print(B, splitInv, i, j)




# +



# -

# # Test Cases
#
# TEST CASE - 1  
#
# A - {1,3,5,2,4,6}  
#
# ANS - 3  
#
# TEST CASE - 2  
#
# A- {1,5,3,2,4}  
#
# ANS - 4  
#
# TEST CASE - 3  
#
# A- {5,4,3,2,1}  
#
# ANS - 10
#
# TEST CASE - 4
#
# A - {1,6,3,2,4,5}
#
# ANS - 5
#
# soesilo w:
#
# Test Case - #1 - 15 numbers
#
# A - { 9, 12, 3, 1, 6, 8, 2, 5, 14, 13, 11, 7, 10, 4, 0 }
#
# Ans - 56
#
# Test Case - #2 - 50 numbers
#
# A - { 37, 7, 2, 14, 35, 47, 10, 24, 44, 17, 34, 11, 16, 48, 1, 39, 6, 33, 43, 26, 40, 4, 28, 5, 38, 41, 42, 12, 13, 21, 29, 18, 3, 19, 0, 32, 46, 27, 31, 25, 15, 36, 20, 8, 9, 49, 22, 23, 30, 45 }
#
# Ans - 590
#
# Test Case - #3 - 100 numbers
#
# { 4, 80, 70, 23, 9, 60, 68, 27, 66, 78, 12, 40, 52, 53, 44, 8, 49, 28, 18, 46, 21, 39, 51, 7, 87, 99, 69, 62, 84, 6, 79, 67, 14, 98, 83, 0, 96, 5, 82, 10, 26, 48, 3, 2, 15, 92, 11, 55, 63, 97, 43, 45, 81, 42, 95, 20, 25, 74, 24, 72, 91, 35, 86, 19, 75, 58, 71, 47, 76, 59, 64, 93, 17, 50, 56, 94, 90, 89, 32, 37, 34, 65, 1, 73, 41, 36, 57, 77, 30, 22, 13, 29, 38, 16, 88, 61, 31, 85, 33, 54 }
#
# Ans - 2372

# +
#initArray = [1, 3, 5, 2, 4, 6] // returns 3.
initArray = [1,6,3,2,4,5] # should return 4 
mergeAndCountSplitInv(initArray)

def mergeAndCountSplitInv(someArray):
    print("hello")
    B = []
    #C = [1, 3, 5]
    #D = [2, 4, 6]
    C = someArray[:len(someArray)//2]
    D = someArray[len(someArray)//2:]
    print(C, D)
    i = 0
    j = 0
    splitInv = 0
    
    for k in range(0, len(someArray)):
        if C[i] < D[j]:
            print(k , i)
            #B[k] = C[i]
            B.insert(k, C[i])
            i = i + 1
        else:
            #B[k] = D[j]
            B.insert(k, D[j])
            j = j + 1
            splitInv = splitInv + ((len(initArray) / 2) - i)  #refactor to be dynamic to array size

        print(B, splitInv, i, j)


# +
#initArray = [1, 3, 5, 2, 4, 6] // returns 3.
initArray = [1,6,3,2,4,5] # should return 4 
mergeAndCountSplitInv(initArray)

def mergeAndCountSplitInv(someArray):
    print("hello")
    B = []
    #C = [1, 3, 5]
    #D = [2, 4, 6]
    C = someArray[:len(someArray)//2]
    D = someArray[len(someArray)//2:]
    print(C, D)
    i = 0
    j = 0
    splitInv = 0
    
    for k in range(0, len(someArray)):
        if C[i] < D[j]:
            print(k , i)
            #B[k] = C[i]
            B.insert(k, C[i])
            i = i + 1
        else:
            #B[k] = D[j]
            B.insert(k, D[j])
            j = j + 1
            splitInv = splitInv + ((len(initArray) / 2) - i)  #refactor to be dynamic to array size

        print(B, splitInv, i, j)
# -



StarcoderdataJupyterScriptsDedupFiltered