#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(16) AS LONG
    LOCAL temp(16) AS LONG
    LOCAL n AS LONG
    LOCAL size_val AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL k AS LONG
    LOCAL low AS LONG
    LOCAL mid AS LONG
    LOCAL high_val AS LONG
    LOCAL temp_val AS LONG
    LOCAL temp_str AS STRING

    n = 8
    arr(0) = 37
    arr(1) = 12
    arr(2) = 85
    arr(3) = 3
    arr(4) = 42
    arr(5) = 19
    arr(6) = 64
    arr(7) = 51

    PRINT "Bitonic Sort (Sorting Network)"
    PRINT "=============================="
    PRINT ""

    PRINT "Before:"
    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT temp_str
    PRINT ""

    ' Bitonic sort
    size_val = 2
    WHILE size_val <= n
        k = size_val / 2
        WHILE k > 0
            i = 0
            WHILE i < n
                j = i XOR k
                IF j > i THEN
                    IF ((i AND size_val) = 0) THEN
                        IF arr(i) > arr(j) THEN
                            temp_val = arr(i)
                            arr(i) = arr(j)
                            arr(j) = temp_val
                        END IF
                    ELSE
                        IF arr(i) < arr(j) THEN
                            temp_val = arr(i)
                            arr(i) = arr(j)
                            arr(j) = temp_val
                        END IF
                    END IF
                END IF
                i = i + 1
            WEND
            k = k / 2
        WEND
        size_val = size_val * 2
    WEND

    PRINT "After (ascending):"
    temp_str = ""
    i = 0
    WHILE i < n
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    PRINT temp_str

    ' Verify sorted
    i = 0
    j = 1
    WHILE i < n - 1
        IF arr(i) > arr(i + 1) THEN
            j = 0
        END IF
        i = i + 1
    WEND
    IF j = 1 THEN
        PRINT "Verified: correctly sorted"
    ELSE
        PRINT "NOT correctly sorted"
    END IF

    ' Test bitonic property on larger array
    n = 16
    arr(0) = 95
    arr(1) = 23
    arr(2) = 47
    arr(3) = 11
    arr(4) = 72
    arr(5) = 38
    arr(6) = 59
    arr(7) = 4
    arr(8) = 88
    arr(9) = 15
    arr(10) = 63
    arr(11) = 29
    arr(12) = 41
    arr(13) = 76
    arr(14) = 32
    arr(15) = 54

    size_val = 2
    WHILE size_val <= n
        k = size_val / 2
        WHILE k > 0
            i = 0
            WHILE i < n
                j = i XOR k
                IF j > i THEN
                    IF ((i AND size_val) = 0) THEN
                        IF arr(i) > arr(j) THEN
                            temp_val = arr(i)
                            arr(i) = arr(j)
                            arr(j) = temp_val
                        END IF
                    ELSE
                        IF arr(i) < arr(j) THEN
                            temp_val = arr(i)
                            arr(i) = arr(j)
                            arr(j) = temp_val
                        END IF
                    END IF
                END IF
                i = i + 1
            WEND
            k = k / 2
        WEND
        size_val = size_val * 2
    WEND

    PRINT ""
    PRINT "16-element sort:"
    temp_str = ""
    i = 0
    WHILE i < n
        IF i > 0 AND i MOD 8 = 0 THEN
            PRINT temp_str
            temp_str = ""
        END IF
        temp_str = temp_str + STR$(arr(i))
        IF i < n - 1 AND i MOD 8 <> 7 THEN temp_str = temp_str + " "
        i = i + 1
    WEND
    IF temp_str <> "" THEN PRINT temp_str

    PRINT ""
    PRINT "Bitonic sort complete."

    FUNCTION = 0
END FUNCTION
