#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    LOCAL arr(128) AS LONG
    LOCAL temp(128) AS LONG
    LOCAL n AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL k AS LONG
    LOCAL left_start AS LONG
    LOCAL right_start AS LONG
    LOCAL left_end AS LONG
    LOCAL right_end AS LONG
    LOCAL width AS LONG
    LOCAL idx AS LONG
    LOCAL temp_str AS STRING

    ' Iterative (bottom-up) merge sort

    n = 16
    arr(0) = 38
    arr(1) = 27
    arr(2) = 43
    arr(3) = 3
    arr(4) = 9
    arr(5) = 82
    arr(6) = 10
    arr(7) = 55
    arr(8) = 91
    arr(9) = 16
    arr(10) = 74
    arr(11) = 61
    arr(12) = 25
    arr(13) = 47
    arr(14) = 33
    arr(15) = 58

    PRINT "Iterative Merge Sort (Bottom-Up)"
    PRINT "================================"
    PRINT ""

    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 "Before: " + temp_str

    ' Bottom-up merge sort
    width = 1
    WHILE width < n
        i = 0
        WHILE i < n
            left_start = i
            left_end = i + width - 1
            IF left_end >= n THEN left_end = n - 1
            right_start = i + width
            right_end = i + 2 * width - 1
            IF right_end >= n THEN right_end = n - 1
            IF right_start >= n THEN
                i = i + 2 * width
            ELSE
                ' Merge arr[left..left_end] and arr[right..right_end] into temp
                idx = left_start
                j = left_start
                k = right_start

                WHILE j <= left_end AND k <= right_end
                    IF arr(j) <= arr(k) THEN
                        temp(idx) = arr(j)
                        j = j + 1
                    ELSE
                        temp(idx) = arr(k)
                        k = k + 1
                    END IF
                    idx = idx + 1
                WEND

                WHILE j <= left_end
                    temp(idx) = arr(j)
                    idx = idx + 1
                    j = j + 1
                WEND

                WHILE k <= right_end
                    temp(idx) = arr(k)
                    idx = idx + 1
                    k = k + 1
                WEND

                j = left_start
                WHILE j <= right_end
                    arr(j) = temp(j)
                    j = j + 1
                WEND

                i = i + 2 * width
            END IF
        WEND
        width = width * 2
    WEND

    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 "After:  " + temp_str

    ' Verify
    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 "Sorted correctly"
    ELSE
        PRINT "NOT sorted"
    END IF

    ' Test with odd length
    n = 11
    arr(0) = 73
    arr(1) = 18
    arr(2) = 46
    arr(3) = 91
    arr(4) = 25
    arr(5) = 64
    arr(6) = 37
    arr(7) = 52
    arr(8) = 80
    arr(9) = 11
    arr(10) = 69

    PRINT ""
    PRINT "Odd-length test (11 elements):"
    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 "Before: " + temp_str

    width = 1
    WHILE width < n
        i = 0
        WHILE i < n
            left_start = i
            left_end = i + width - 1
            IF left_end >= n THEN left_end = n - 1
            right_start = i + width
            right_end = i + 2 * width - 1
            IF right_end >= n THEN right_end = n - 1
            IF right_start < n THEN
                idx = left_start
                j = left_start
                k = right_start

                WHILE j <= left_end AND k <= right_end
                    IF arr(j) <= arr(k) THEN
                        temp(idx) = arr(j)
                        j = j + 1
                    ELSE
                        temp(idx) = arr(k)
                        k = k + 1
                    END IF
                    idx = idx + 1
                WEND

                WHILE j <= left_end
                    temp(idx) = arr(j)
                    idx = idx + 1
                    j = j + 1
                WEND

                WHILE k <= right_end
                    temp(idx) = arr(k)
                    idx = idx + 1
                    k = k + 1
                WEND

                j = left_start
                WHILE j <= right_end
                    arr(j) = temp(j)
                    j = j + 1
                WEND
            END IF
            i = i + 2 * width
        WEND
        width = width * 2
    WEND

    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 "After:  " + temp_str

    PRINT ""
    PRINT "Iterative merge sort complete."

    FUNCTION = 0
END FUNCTION
