maxvals%=1001
count%=0
heaps%=0
intros%=0
inserts%=0
DIM values%(maxvals%)
PRINT "======INTROSORT GFA BASIC======="
load_file("INPUT.TXT")
elapsed!=@do_sort
save_file("OUTPUT.TXT")
PRINT "==========RUN COMPLETE=========="
PRINT "INTROSORT TOOK ";elapsed!;" SECONDS."
PRINT "================================"
PRINT "SORT CALLED | TIMES"
PRINT "------------+-------------------"
PRINT "Intro       | ";intros%
PRINT "Inserts     | ";inserts%
PRINT "Heaps       | ";heaps%
PRINT "================================"
REM -------------------------------------------------------------------
REM load_file
REM Purpose:
REM   Read non-blank integer records from the named input file into the program collection or shared array.
REM Parameters:
REM   filespec$ - path of the input file to read.
REM Returns:
REM   No value; fills values% and updates count%.
REM Side effects:
REM   Opens and closes the input file, populates the collection or shared array, and may update its element count.
REM -------------------------------------------------------------------
PROCEDURE load_file(filespec$)
  PRINT "READING INPUT FILE...";
  DIM line$(80)
  OPEN "i",#1,filespec$
  DO WHILE NOT EOF(#1)
    INPUT #1,line$
    IF line$<>"" THEN
      values%(count%)=VAL(line$)
      count%=count%+1
    ENDIF
  LOOP
  CLOSE #1
  PRINT "DONE."
RETURN
REM -------------------------------------------------------------------
REM save_file
REM Purpose:
REM   Write the sorted integer collection or shared array to the named output file, one value per line.
REM Parameters:
REM   filespec$ - path of the output file to create or replace.
REM Returns:
REM   No value; writes the output file.
REM Side effects:
REM   Creates or replaces the output file and reports file progress.
REM -------------------------------------------------------------------
PROCEDURE save_file(filespec$)
  PRINT "SAVING OUTPUT FILE...";
  OPEN "o",#1,filespec$
  FOR v%=0 TO count%-1
    PRINT #1,STR$(values%(v%))
  NEXT v%
  CLOSE #1
  PRINT "DONE."
RETURN
REM -------------------------------------------------------------------
REM sift_down
REM Purpose:
REM   Restore max-heap order below the specified root within the active heap range.
REM Parameters:
REM   root% - current root index to sift down in the heap.
REM   sindex% - inclusive first index of the active heap range.
REM   eindex% - exclusive end index of the active heap range.
REM Returns:
REM   No value; rearranges the range in place.
REM Side effects:
REM   Mutates the sequence and may stop once the heap property is restored.
REM -------------------------------------------------------------------
PROCEDURE sift_down(root%,sindex%,eindex%)
  LOCAL child%,temp%
  DO WHILE sindex%+2*(root%-sindex%)+1<eindex%
    child%=sindex%+2*(root%-sindex%)+1
    IF child%+1<eindex% AND values%(child%)<values%(child%+1) THEN
      child%=child%+1
    ENDIF
    EXIT IF values%(root%)>=values%(child%)
    temp%=values%(root%)
    values%(root%)=values%(child%)
    values%(child%)=temp%
    root%=child%
  LOOP
RETURN
REM -------------------------------------------------------------------
REM heap_sort
REM Purpose:
REM   Sort the selected range in place with heapsort, the worst-case introsort fallback.
REM Parameters:
REM   sindex% - inclusive first index of the range to sort.
REM   eindex% - exclusive end index of the range to sort.
REM Returns:
REM   No value; sorts the selected range in place.
REM Side effects:
REM   Mutates the range and increments the heapsort counter where present.
REM -------------------------------------------------------------------
PROCEDURE heap_sort(sindex%,eindex%)
  heaps%=heaps%+1
  LOCAL r%,root%,last%,temp%
  r%=(sindex%+(eindex%-sindex%) DIV 2)-1
  FOR root%=r% TO sindex% STEP -1
    sift_down(root%,sindex%,eindex%)
  NEXT root%
  FOR last%=eindex%-1 TO sindex%+1 STEP -1
    temp%=values%(sindex%)
    values%(sindex%)=values%(last%)
    values%(eindex%)=temp%
    sift_down(sindex%,sindex%,last%)
  NEXT last%
RETURN
REM -------------------------------------------------------------------
REM insert_sort
REM Purpose:
REM   Sort the selected range in place with insertion sort, which is efficient for short ranges.
REM Parameters:
REM   sindex% - inclusive first index of the range to sort.
REM   eindex% - exclusive end index of the range to sort.
REM Returns:
REM   No value; sorts the selected range in place.
REM Side effects:
REM   Mutates the range and increments the insertion-sort counter where present.
REM -------------------------------------------------------------------
PROCEDURE insert_sort(sindex%,eindex%)
  inserts%=inserts%+1
  LOCAL index%,value%,pos%,dpos%
  FOR index%=sindex%+1 TO eindex%-1
    value%=values%(index%)
    pos%=index%-1
    dpos%=0
    DO WHILE dpos%=0
      IF pos%<sindex% THEN
        dpos%=1
      ELSE
        IF values%(pos%)<=value% THEN
          dpos%=1
        ELSE
          values%(pos%+1)=values%(pos%)
          pos%=pos%-1
        ENDIF
      ENDIF
    LOOP
    values%(pos%+1)=value%
  NEXT index%
RETURN
REM -------------------------------------------------------------------
REM partition
REM Purpose:
REM   Partition the selected range around its middle-element pivot and return the first index of the right-hand range.
REM Parameters:
REM   sindex% - inclusive first index of the range to partition.
REM   eindex% - exclusive end index of the range to partition.
REM Returns:
REM   The first index of the right partition, which is also the left boundary of the recursive ranges.
REM Side effects:
REM   Reorders the range in place while inward scans keep each access inside the active bounds.
REM -------------------------------------------------------------------
FUNCTION partition(sindex%,eindex%)
  LOCAL left%,right%,pivot%,temp%,rang%
  left%=sindex%
  right%=eindex%-1
  rang%=sindex%+(eindex%-sindex%) DIV 2
  pivot%=values%(rang%)
  DO WHILE left%<=right%
    DO WHILE values%(left%)<pivot%
      left%=left%+1
    LOOP
    DO WHILE values%(right%)>pivot%
      right%=right%-1
    LOOP
    IF left%<=right% THEN
      temp%=values%(left%)
      values%(left%)=values%(right%)
      values%(right%)=temp%
      left%=left%+1
      right%=right%-1
    ENDIF
  LOOP
  RETURN left%
ENDFUNC
REM -------------------------------------------------------------------
REM intro_sort
REM Purpose:
REM   Sort the selected range in place: insertion sort for short ranges, heapsort when the depth budget expires, otherwise partition and recurse.
REM Parameters:
REM   sindex% - inclusive first index of the range to sort.
REM   eindex% - exclusive end index of the range to sort.
REM   maxdepth% - remaining partition budget before heapsort fallback.
REM Returns:
REM   No value; sorts the selected range in place.
REM Side effects:
REM   Mutates the range and updates the introsort counter; recursive calls reduce the depth budget.
REM -------------------------------------------------------------------
PROCEDURE intro_sort(sindex%,eindex%,maxdepth%)
  intros%=intros%+1
  LOCAL length%,part%,lend%
  length%=eindex%-sindex%
  IF length%>1 THEN
    IF length%<16 THEN
      insert_sort(sindex%,eindex%)
    ELSE
      IF maxdepth%<=0 THEN
        heap_sort(sindex%,eindex%)
      ELSE
        part%=@partition(sindex%,eindex%)
        intro_sort(sindex%,part%,maxdepth%-1)
        intro_sort(part%,eindex%,maxdepth%-1)
      ENDIF
    ENDIF
  ENDIF
RETURN
REM -------------------------------------------------------------------
REM log2
REM Purpose:
REM   Compute the integer base-2 size estimate used to initialize introsort depth.
REM Parameters:
REM   v% - positive integer used to calculate the depth estimate.
REM Returns:
REM   An integer base-2 size estimate.
REM Side effects:
REM   Does not modify the input.
REM -------------------------------------------------------------------
FUNCTION log2(v%)
  LOCAL num%
  num%=0
  DO WHILE v%>0
    v%=v% DIV 2
    num%=num%+1
  LOOP
  RETURN num%
ENDFUNC
REM -------------------------------------------------------------------
REM do_sort
REM Purpose:
REM   Choose the initial depth budget, time the top-level introsort, and report completion.
REM Parameters:
REM None; this routine uses shared state or its enclosing context.
REM Returns:
REM   Elapsed time measured by this implementation.
REM Side effects:
REM   Starts and stops a timer, prints progress, and invokes introsort on the full sequence.
REM -------------------------------------------------------------------
FUNCTION do_sort
  PRINT "SORTING ELEMENTS...";
  stime!=TIMER
  maxdepth%=0
  IF count%>1 THEN
    maxdepth%=@log2(count%) DIV 2
  ENDIF
  intro_sort(0,count%,maxdepth%)
  etime!=TIMER
  PRINT "DONE."
  RETURN etime!-stime!
ENDFUNC