' Recursive Sort — Quicksort and mergesort all in PBMAIN
#COMPILE EXE
#DIM ALL

FUNCTION PBMAIN() AS LONG
    DIM nums(1 TO 10) AS LONG
    DIM stk(1 TO 100) AS LONG
    DIM la(1 TO 10) AS LONG
    DIM ra(1 TO 10) AS LONG
    LOCAL i AS LONG
    LOCAL j AS LONG
    LOCAL aPos AS LONG
    LOCAL bPos AS LONG
    LOCAL temp AS LONG
    LOCAL pivot AS LONG
    LOCAL pivotIdx AS LONG
    LOCAL sp AS LONG
    LOCAL n AS LONG
    LOCAL outLine AS STRING
    LOCAL mid AS LONG
    LOCAL n1 AS LONG
    LOCAL n2 AS LONG
    LOCAL k AS LONG
    LOCAL idx AS LONG

    PRINT "======================="
    PRINT " Recursive Sort Demo"
    PRINT "======================="
    PRINT

    nums(1) = 42
    nums(2) = 7
    nums(3) = 99
    nums(4) = 13
    nums(5) = 55
    nums(6) = 3
    nums(7) = 88
    nums(8) = 24
    nums(9) = 61
    nums(10) = 17
    n = 10

    PRINT "=== QUICKSORT ==="
    outLine = ""
    FOR i = 1 TO n
        outLine = outLine & STR$(nums(i)) & " "
    NEXT i
    PRINT "Before: " & outLine

    sp = 1
    stk(sp) = 1
    sp = sp + 1
    stk(sp) = n
    DO
        IF sp = 1 THEN EXIT DO
        bPos = stk(sp)
        sp = sp - 1
        aPos = stk(sp)
        sp = sp - 1
        IF aPos < bPos THEN
            pivotIdx = (aPos + bPos) / 2
            pivot = nums(pivotIdx)
            i = aPos
            j = bPos
            DO
                DO WHILE nums(i) < pivot
                    i = i + 1
                LOOP
                DO WHILE nums(j) > pivot
                    j = j - 1
                LOOP
                IF i <= j THEN
                    temp = nums(i)
                    nums(i) = nums(j)
                    nums(j) = temp
                    i = i + 1
                    j = j - 1
                END IF
            LOOP UNTIL i > j
            IF aPos < j THEN
                sp = sp + 1
                stk(sp) = aPos
                sp = sp + 1
                stk(sp) = j
            END IF
            IF i < bPos THEN
                sp = sp + 1
                stk(sp) = i
                sp = sp + 1
                stk(sp) = bPos
            END IF
        END IF
    LOOP

    outLine = ""
    FOR i = 1 TO n
        outLine = outLine & STR$(nums(i)) & " "
    NEXT i
    PRINT "After:  " & outLine
    PRINT

    nums(1) = 73
    nums(2) = 14
    nums(3) = 61
    nums(4) = 28
    nums(5) = 45
    nums(6) = 91
    nums(7) = 8
    nums(8) = 57
    nums(9) = 33
    nums(10) = 82
    n = 10

    PRINT "=== MERGESORT ==="
    outLine = ""
    FOR i = 1 TO n
        outLine = outLine & STR$(nums(i)) & " "
    NEXT i
    PRINT "Before: " & outLine

    k = 1
    DO
        IF k >= n THEN EXIT DO
        i = 1
        DO
            IF i > n - k THEN EXIT DO
            aPos = i
            mid = i + k - 1
            bPos = i + 2 * k - 1
            IF bPos > n THEN bPos = n
            n1 = mid - aPos + 1
            n2 = bPos - mid
            FOR sp = 1 TO n1
                la(sp) = nums(aPos + sp - 1)
            NEXT sp
            FOR sp = 1 TO n2
                ra(sp) = nums(mid + sp)
            NEXT sp
            sp = 1
            j = 1
            idx = aPos
            DO
                IF sp > n1 OR j > n2 THEN EXIT DO
                IF la(sp) <= ra(j) THEN
                    nums(idx) = la(sp)
                    sp = sp + 1
                ELSE
                    nums(idx) = ra(j)
                    j = j + 1
                END IF
                idx = idx + 1
            LOOP
            DO
                IF sp > n1 THEN EXIT DO
                nums(idx) = la(sp)
                sp = sp + 1
                idx = idx + 1
            LOOP
            DO
                IF j > n2 THEN EXIT DO
                nums(idx) = ra(j)
                j = j + 1
                idx = idx + 1
            LOOP
            i = aPos + 2 * k
        LOOP
        k = k + k
    LOOP

    outLine = ""
    FOR i = 1 TO n
        outLine = outLine & STR$(nums(i)) & " "
    NEXT i
    PRINT "After:  " & outLine
    PRINT

    PRINT "Recursive sort complete."
    FUNCTION = 0
END FUNCTION
