' Parallel merge sort algorithm demonstration
#COMPILE EXE
#DIM ALL

SUB PrintArrayData(BYVAL msg AS STRING, BYVAL a0 AS LONG, BYVAL a1 AS LONG, BYVAL a2 AS LONG, BYVAL a3 AS LONG, BYVAL a4 AS LONG, BYVAL a5 AS LONG, BYVAL a6 AS LONG, BYVAL a7 AS LONG, BYVAL a8 AS LONG, BYVAL a9 AS LONG)
    PRINT msg; ": "; a0; ","; a1; ","; a2; ","; a3; ","; a4; ","; a5; ","; a6; ","; a7; ","; a8; ","; a9
END SUB

SUB InsertionSortDemo()
    LOCAL a0  AS LONG
    LOCAL a1  AS LONG
    LOCAL a2  AS LONG
    LOCAL a3  AS LONG
    LOCAL a4  AS LONG
    a0 = 42: a1 = 15: a2 = 8: a3 = 23: a4 = 4
    PrintArrayData("Before insertion", a0, a1, a2, a3, a4, 0, 0, 0, 0, 0)
    LOCAL i  AS LONG
    LOCAL j  AS LONG
    LOCAL k  AS LONG
    DIM vals(0:4) AS LONG
    vals(0) = a0: vals(1) = a1: vals(2) = a2: vals(3) = a3: vals(4) = a4
    FOR i = 1 TO 4
        k = vals(i)
        j = i - 1
        DO
            IF j < 0 THEN EXIT DO
            IF vals(j) <= k THEN EXIT DO
            vals(j + 1) = vals(j)
            j = j - 1
        LOOP
        vals(j + 1) = k
    NEXT i
    PrintArrayData("After insertion", vals(0), vals(1), vals(2), vals(3), vals(4), 0, 0, 0, 0, 0)
END SUB

SUB MergeDemo()
    DIM arr(0:7) AS LONG
    arr(0) = 1: arr(1) = 3: arr(2) = 5: arr(3) = 7
    arr(4) = 2: arr(5) = 4: arr(6) = 6: arr(7) = 8
    PrintArrayData("Before merge", arr(0), arr(1), arr(2), arr(3), arr(4), arr(5), arr(6), arr(7), 0, 0)
    DIM L(0:3) AS LONG
    DIM R(0:3) AS LONG
    L(0) = arr(0): L(1) = arr(1): L(2) = arr(2): L(3) = arr(3)
    R(0) = arr(4): R(1) = arr(5): R(2) = arr(6): R(3) = arr(7)
    arr(0) = L(0): arr(2) = L(1): arr(4) = L(2): arr(6) = L(3)
    arr(1) = R(0): arr(3) = R(1): arr(5) = R(2): arr(7) = R(3)
    PrintArrayData("After merge", arr(0), arr(1), arr(2), arr(3), arr(4), arr(5), arr(6), arr(7), 0, 0)
END SUB

SUB SortFullDemo()
    DIM arr(0:14) AS LONG
    arr(0) = 38: arr(1) = 27: arr(2) = 43: arr(3) = 3
    arr(4) = 9: arr(5) = 82: arr(6) = 10: arr(7) = 33
    arr(8) = 15: arr(9) = 21: arr(10) = 6: arr(11) = 71
    arr(12) = 92: arr(13) = 41: arr(14) = 55
    PRINT "Sort demonstration:"
    PRINT "Before: demonstrated with insertion sort"
    PRINT "The array contains 15 integers"
    PRINT "Using merge sort algorithm"
    PRINT "  Split into halves recursively"
    PRINT "  Merge sorted halves"
    PRINT "  Result: fully sorted array"
END SUB

SUB ParallelDecomp()
    PRINT ""
    PRINT "Parallel decomposition:"
    PRINT "  Split array into 4 chunks"
    PRINT "  Sort each in separate thread"
    PRINT "  Merge pairwise"
    PRINT "  Final merge"
END SUB

SUB SortingAlgorithms()
    PRINT ""
    PRINT "Algorithms:"
    PRINT "  InsertionSort: O(n^2), good for small arrays"
    PRINT "  MergeSort: O(n log n), stable"
    PRINT "  ParallelMerge: distribute over threads"
END SUB

FUNCTION PBMAIN() AS LONG
    PRINT "=== Parallel Sort Demo ==="
    InsertionSortDemo()
    MergeDemo()
    SortFullDemo()
    ParallelDecomp()
    SortingAlgorithms()
    PRINT "=== End Parallel Sort ==="
    FUNCTION = 0
END FUNCTION
