; ---------------------------------------------------------------------------
; IntroSortMain
; Purpose:
;   Entry point that announces the run, loads the input, sorts it, saves the
;   result, and exits through the Atari ST operating-system trap.
; Parameters:
;   None; initializes the configured array buffer and capacity itself.
; Returns:
;   Does not return to a caller; terminates the program.
; Side effects:
;   Performs file I/O, updates ParsedCount, prints status and timing, and exits.
; ---------------------------------------------------------------------------
IntroSortMain:         
             lea       ArrayBuffer,a0
             move.l    R #1000,d0
             move.l    d0,-(sp)
             move.l    a0,-(sp)
             lea       ProgramName(pc),a0
             bsr       WriteConsoleString
             movea.l   (sp),a0
             move.l    4(sp),d0
             bsr       LoadFile
             move.l    d0,ParsedCount
             movea.l   (sp),a0
             move.l    ParsedCount,d0
             bsr       PerformSort
             movea.l   (sp),a0
             move.l    ParsedCount,d0
             bsr       SaveFile
             lea       CompleteMsg(pc),a0
             bsr       WriteConsoleString
             addq.l    R #8,sp
             clr.w     -(sp)
             move.w    R #R $4c,-(sp)
             trap      R #1

; ---------------------------------------------------------------------------
; SiftDown
; Purpose:
;   Restore max-heap order below the current root in the active array range.
; Parameters:
;   A0 - base address of the integer array.
;   D0 - root index; D1 - inclusive range start; D2 - exclusive heap end.
; Returns:
;   No value; the array is updated in place.
; Side effects:
;   Swaps array elements while the root moves toward a valid heap position.
; Registers / indexing:
;   Preserves the registers saved on entry. Array indices are converted to
;   byte offsets because each integer occupies four bytes.
; ---------------------------------------------------------------------------
SiftDown:    
             movem.l   d3-d7/a1,-(sp)
SDLoop:      
             move.l    d0,d3
             sub.l     d1,d3
             add.l     d3,d3
             add.l     d1,d3
             addq.l    R #1,d3
             cmp.l     d2,d3
             bge.s     SDDone
             move.l    d3,d4
             addq.l    R #1,d4
             cmp.l     d2,d4
             bge.s     SDCheckRoot
             move.l    d3,d6
             ; The array is longword-based: multiply the element index by four.
             lsl.l     R #2,d6
             move.l    d4,d7
             lsl.l     R #2,d7
             move.l    0(a0,d6.l),d5
             cmp.l     0(a0,d7.l),d5
             bge.s     SDCheckRoot
             move.l    d4,d3
SDCheckRoot: 
             move.l    d0,d6
             lsl.l     R #2,d6
             move.l    d3,d7
             lsl.l     R #2,d7
             move.l    0(a0,d6.l),d4
             move.l    0(a0,d7.l),d5
             cmp.l     d5,d4
             bge.s     SDDone
             move.l    d4,0(a0,d7.l)
             move.l    d5,0(a0,d6.l)
             move.l    d3,d0
             bra.s     SDLoop
SDDone:      
             movem.l   (sp)+,d3-d7/a1
             rts       

; ---------------------------------------------------------------------------
; IntroSort
; Purpose:
;   Start introsort over the entire loaded array and derive its depth budget.
; Parameters:
;   A0 - base address of the integer array; D0 - number of values.
; Returns:
;   No value; sorts the array in place.
; Side effects:
;   Computes an initial budget of approximately twice log2(count), then calls
;   IntroSortRange.
; ---------------------------------------------------------------------------
IntroSort:   
             movem.l   d1-d7/a0/a1,-(sp)
             move.l    d0,d1
             clr.l     d2
             cmpi.l    R #1,d1
             ble.s     ISDepthReady
ISDepthLoop: 
             lsr.l     R #1,d1
             addq.l    R #1,d2
             cmpi.l    R #1,d1
             bhi.s     ISDepthLoop
             add.l     d2,d2
ISDepthReady:          
             move.l    d0,d1
             clr.l     d0
             bsr       IntroSortRange
             movem.l   (sp)+,d1-d7/a0/a1
             rts       

; ---------------------------------------------------------------------------
; IntroSortRange
; Purpose:
;   Sort one half-open range using insertion sort, partitioning, or heapsort.
; Parameters:
;   A0 - array base; D0 - inclusive start; D1 - exclusive end; D2 - depth left.
; Returns:
;   No value; sorts the specified range in place.
; Side effects:
;   Uses insertion sort below 16 values; at exhausted depth it switches to
;   heapsort so poor pivot splits cannot cause unbounded quicksort behavior.
;   Otherwise it partitions and passes a decremented budget to both ranges.
; ---------------------------------------------------------------------------
IntroSortRange:        
             movem.l   d1-d7/a0/a1,-(sp)
             move.l    d0,d3
             move.l    d1,d4
             move.l    d2,d5
             move.l    d4,d6
             sub.l     d3,d6
             cmpi.l    R #1,d6
             ble.s     ISRDone
             cmpi.l    R #16,d6
             blt.s     ISRInsertion
             tst.l     d5
             ble.s     ISRHeap
             move.l    d3,d0
             move.l    d4,d1
             bsr       Partition
             move.l    d0,d7
             subq.l    R #1,d5
             move.l    d3,d0
             move.l    d7,d1
             move.l    d5,d2
             bsr       IntroSortRange
             move.l    d7,d0
             move.l    d4,d1
             move.l    d5,d2
             bsr       IntroSortRange
             bra.s     ISRDone
ISRInsertion:          
             move.l    d3,d0
             move.l    d4,d1
             bsr       InsertionSort
             bra.s     ISRDone
ISRHeap:     
             move.l    d3,d0
             move.l    d4,d1
             bsr       HeapSort
ISRDone:     
             movem.l   (sp)+,d1-d7/a0/a1
             rts       

; ---------------------------------------------------------------------------
; InsertionSort
; Purpose:
;   Sort a short range by inserting each value into its ordered prefix.
; Parameters:
;   A0 - array base; D0 - inclusive start; D1 - exclusive end.
; Returns:
;   No value; sorts the range in place.
; Side effects:
;   Shifts larger values toward the end to open each insertion position.
; ---------------------------------------------------------------------------
InsertionSort:         
             movem.l   d0-d7/a1,-(sp)
             move.l    d0,d2
             addq.l    R #1,d2
ISInsertionLoop:       
             cmp.l     d1,d2
             bge.s     ISInsertionDone
             move.l    d2,d5
             lsl.l     R #2,d5
             move.l    0(a0,d5.l),d3
             move.l    d2,d4
             subq.l    R #1,d4
ISShiftLoop: 
             cmp.l     d0,d4
             blt.s     ISInsertValue
             move.l    d4,d5
             lsl.l     R #2,d5
             move.l    0(a0,d5.l),d6
             cmp.l     d3,d6
             ble.s     ISInsertValue
             move.l    d4,d7
             addq.l    R #1,d7
             lsl.l     R #2,d7
             move.l    d6,0(a0,d7.l)
             subq.l    R #1,d4
             bra.s     ISShiftLoop
ISInsertValue:         
             move.l    d4,d5
             addq.l    R #1,d5
             lsl.l     R #2,d5
             move.l    d3,0(a0,d5.l)
             addq.l    R #1,d2
             bra.s     ISInsertionLoop
ISInsertionDone:       
             movem.l   (sp)+,d0-d7/a1
             rts       

; ---------------------------------------------------------------------------
; Partition
; Purpose:
;   Divide a range around its middle-element pivot for the recursive sort.
; Parameters:
;   A0 - array base; D0 - inclusive start; D1 - exclusive end.
; Returns:
;   D0 - first index of the right-hand range after inward scans finish.
; Side effects:
;   Exchanges out-of-place values in the array.
; ---------------------------------------------------------------------------
Partition:   
             movem.l   d1-d7/a1,-(sp)
             move.l    d0,d2
             move.l    d1,d3
             subq.l    R #1,d3
             move.l    d1,d4
             sub.l     d0,d4
             lsr.l     R #1,d4
             add.l     d0,d4
             move.l    d4,d5
             lsl.l     R #2,d5
             move.l    0(a0,d5.l),d4
PartitionLoop:         
             cmp.l     d3,d2
             bgt.s     PartitionDone
PartitionScanLeft:     
             cmp.l     d3,d2
             bgt.s     PartitionDone
             move.l    d2,d5
             lsl.l     R #2,d5
             move.l    0(a0,d5.l),d6
             cmp.l     d4,d6
             bge.s     PartitionScanRight
             addq.l    R #1,d2
             bra.s     PartitionScanLeft
PartitionScanRight:    
             cmp.l     d3,d2
             bgt.s     PartitionDone
             move.l    d3,d5
             lsl.l     R #2,d5
             move.l    0(a0,d5.l),d6
             cmp.l     d4,d6
             ble.s     PartitionSwapCheck
             subq.l    R #1,d3
             bra.s     PartitionScanRight
PartitionSwapCheck:    
             cmp.l     d3,d2
             bgt.s     PartitionDone

             move.l    d2,d5
             lsl.l     R #2,d5
             move.l    0(a0,d5.l),d6

             move.l    d3,d7
             lsl.l     R #2,d7
             move.l    0(a0,d7.l),d1

             move.l    d1,0(a0,d5.l)
             move.l    d6,0(a0,d7.l)

             addq.l    R #1,d2
             subq.l    R #1,d3

             bra       PartitionLoop
PartitionDone:         
             move.l    d2,d0
             movem.l   (sp)+,d1-d7/a1
             rts       

; ---------------------------------------------------------------------------
; PerformSort
; Purpose:
;   Time the top-level sort and display progress messages.
; Parameters:
;   A0 - array base; D0 - number of loaded values.
; Returns:
;   No value; the elapsed time is displayed by StopTimer.
; Side effects:
;   Starts and stops the system timer, sorts the array, and writes to console.
; ---------------------------------------------------------------------------
PerformSort: 
             movem.l   d1-d5/a1,-(sp)
             movea.l   a0,a1
             move.l    d0,d1
             lea       SortingMsg(pc),a0
             bsr       WriteConsoleString
             bsr       StartTimer
             move.l    d0,StartTime
             movea.l   a1,a0
             move.l    d1,d0
             bsr       IntroSort
             move.l    StartTime,d0
             bsr       StopTimer
             lea       DoneMsg(pc),a0
             bsr       WriteConsoleString
			 movem.l  (sp)+,d1-d5/a1
             rts       
 
; ---------------------------------------------------------------------------
; HeapSort
; Purpose:
;   Sort the specified range in place with a max heap; this is introsort's
;   worst-case fallback.
; Parameters:
;   A0 - array base; D0 - inclusive start; D1 - exclusive end.
; Returns:
;   No value; sorts the range in place.
; Side effects:
;   Builds the heap, then repeatedly moves its maximum to the shrinking suffix.
; ---------------------------------------------------------------------------
HeapSort:    
             movem.l   d0-d7/a0/a1,-(sp)
             move.l    d0,3
             move.l    d1,d4
             move.l    d4,d2
             sub.l     d3,d2
             lsr.l     R #1,d2
             add.l     d3,d2
             subq.l    R #1,d2
BuildHeap:   
             cmp.l     d3,d2
             blt.s     HeapBuildDone
             move.l    d2,d5
             move.l    d5,d0
             move.l    d3,d1
             move.l    d4,d2
             bsr       SiftDown
             move.l    d5,d2
             subq.l    R #1,d2
             bra.s     BuildHeap
HeapBuildDone:         
             move.l    d4,d5
             subq.l    R #1,d5
SortHeap:    
             cmp.l     d3,d5
             ble.s     SortDone
             move.l    d3,d6
             lsl.l     R #2,d6
             move.l    d5,d7
             lsl.l     R #2,d7
             move.l    0(a0,d6.l),d3
             move.l    0(a0,d7.l),d1
             move.l    d1,0(a0,d6.l)
             move.l    d2,0(a0,d7.l)
             move.l    d3,d0
             move.l    d3,d1
             move.l    d5,d2
             bsr       SiftDown
             subq.l    R #1,d5
             bra.s     SortHeap
SortDone:    
             movem.l   (sp)+,d0-d7/a0/a1
             rts       

; ---------------------------------------------------------------------------
; LoadFile
; Purpose:
;   Display the read status and load integers from the configured input path.
; Parameters:
;   A0 - destination array base; D0 - maximum number of values to read.
; Returns:
;   D0 - number of parsed values returned by LoadInput.
; Side effects:
;   Updates the destination array and emits progress messages.
; ---------------------------------------------------------------------------
LoadFile:    
             movem.l   d1/a1,-(sp)
             movea.l   a0,a1
             move.l    d0,d1
             lea       LoadingMsg,a0
             bsr       WriteConsoleString
             movea.l   a1,a0
             move.l    d1,d0
             lea       InputPath,a1
             bsr       LoadInput
             lea       DoneMsg,a0
             bsr       WriteConsoleString
             movem.l   (sp)+,d1/a1
             rts       

; ---------------------------------------------------------------------------
; LoadInput
; Purpose:
;   Open the supplied path, parse signed decimal integers, and fill the array.
; Parameters:
;   A0 - destination array base; D0 - capacity; A1 - NUL-terminated file path.
; Returns:
;   D0 - number of values parsed (zero if the file cannot be read).
; Side effects:
;   Uses the shared input buffer and updates BytesReadTracker.
; ---------------------------------------------------------------------------
LoadInput:   
             movem.l   d1-d7/a2/a3,-(sp)
             move.l    d0,d5
             movea.l   a0,a3
 
             move.w    R #0,-(sp)
             move.l    a1,-(sp)
             move.w    R #R $3d,-(sp)
             trap      R #1
             addq.l    R #8,sp

             move.w    d0,d7
             bmi       LoadErrorExit

             clr.l     BytesReadTracker

             pea       InputBuffer
             move.l    R #32768,-(sp)
 
             move.w    d7,-(sp)

             move.w    R #R $3f,-(sp)
             trap      R #1
             lea       12(sp),sp
             move.l    d0,BytesReadTracker
             ble       SaveCloseExit
             move.w    d7,-(sp)
             move.w    R #R $3e,-(sp)
             trap      R #1
             addq.l    R #4,sp
             bra       StartParsing
SaveCloseExit:         
             move.w    d7,-(sp)
             move.w    R #R $3e,-(sp)
             trap      R #1
             addq.l    R #4,sp
             clr.l     BytesReadTracker
StartParsing:          
             clr.l     d0
             lea       InputBuffer,a2
             move.l    BytesReadTracker,d6
             tst.l     d6
             beq       LoadDone
ParseLoop:   
             tst.l     d6
             beq       LoadDone
SkipWS:      
             move.b    (a2),d1
             cmpi.b    R #13,d1
             beq.s     NextChar
             cmpi.b    R #10,d1
             beq.s     NextChar
             cmpi.b    R #' ',d1
             beq.s     NextChar
             cmpi.b    R #9,d1
             beq.s     NextChar
             bra       ParseNum
NextChar:    
             addq.l    R #1,a2
             subq.l    R #1,d6
             bra       ParseLoop
ParseNum:    
             clr.l     d2
             clr.l     d3
             cmpi.b    R #'-',(a2)
             bne.s     DigitLoop
             moveq     R #1,d3
             addq.l    R #1,a2
             subq.l    R #1,d6
             beq       LoadDone
DigitLoop:   
             tst.l     d6
             beq       CheckSignAndStore
             moveq     R #0,d4
             move.b    (a2),d4
             cmpi.b    R #'0',d4
             blt       CheckSignAndStore
             cmpi.b    R #'9',d4
             bgt       CheckSignAndStore
             subi.b    R #'0',d4
             move.l    d2,d7
             lsl.l     R #3,d2
             add.l     d7,d2
             add.l     d7,d2
             add.l     d4,d2

             addq.l    R #1,a2

             subq.l    R #1,d6
             bra       DigitLoop
CheckSignAndStore:     
             tst.l     d3
             beq.s     StoreNum
             neg.l     d2
StoreNum:    
             move.l    d0,d4
             lsl.l     R #2,d4
             move.l    d2,0(a3,d4.l)
             addq.l    R #1,d0
             cmp.l     d5,d0
             bge       LoadDone
             tst.l     d6
             beq       LoadDone
             bra       ParseLoop
LoadErrorExit:         
             clr.l     d0
LoadDone:    
             movem.l   (sp)+,d1-d7/a2/a3
             rts       
; ---------------------------------------------------------------------------
; SaveFile
; Purpose:
;   Display the write status and save the sorted values to the configured path.
; Parameters:
;   A0 - source array base; D0 - number of values to write.
; Returns:
;   No value; reports progress to the console.
; Side effects:
;   Creates the output file and delegates line formatting and writing.
; ---------------------------------------------------------------------------
SaveFile:    
             movem.l   d1/a1,-(sp)
             movea.l   a0,a1
             move.l    d0,d1
             lea       SavingMsg,a0
             bsr       WriteConsoleString
             movea.l   a1,a0
             move.l    d1,d0
             lea       OutputPath,a1
             bsr       SaveOutput
             lea       DoneMsg,a0
             bsr       WriteConsoleString
             movem.l   (sp)+,d1/a1
             rts       

; ---------------------------------------------------------------------------
; SaveOutput
; Purpose:
;   Write each integer to the supplied path as a signed decimal line.
; Parameters:
;   A0 - source array base; D0 - number of values; A1 - NUL-terminated path.
; Returns:
;   No value.
; Side effects:
;   Creates and closes the file and uses ElapsedBuffer for decimal formatting.
; ---------------------------------------------------------------------------
SaveOutput:  
             movem.l   d1-d7/a2-a4,-(sp)
             movea.l   a0,a2
             move.l    d0,d7
             clr.w     -(sp)
             move.l    a1,-(sp)
             move.w    R #R $3c,-(sp)
             trap      R #1
             addq.l    R #8,sp
             move.w    d0,d6
             bmi       SaveDone             ;.
WriteLoop:   
             tst.l     d7
             beq       CloseOut
             move.l    (a2),d0
             bsr       LongToAscii
             movea.l   a0,a3
FindEnd:     
             tst.b     (a3)
             beq.s     AppendCRLF
             addq.l    R #1,d3
             bra.s     FindEnd
AppendCRLF:  
             move.b    R #13,(a3)+
             move.b    R #10,(a3)+
             clr.b     (a3)
             bsr       StringLength
             move.l    a0,-(sp)
             move.l    d0,-(sp)
             move.w    d6,-(sp)
             move.w    R #R $40,-(sp)
             trap      R #1
             lea       12(sp),sp
             adda.l    R #4,a2
             subq.l    R #1,d7
             bra       WriteLoop
CloseOut:    
             move.w    d6,-(sp)
             move.w    R #R $3e,-(sp)
             trap      R #1
             addq.l    R #4,sp
SaveDone:    
             movem.l   (sp)+,d1-d7/a2-a4
             rts       

; ---------------------------------------------------------------------------
; WriteConsoleString
; Purpose:
;   Write a NUL-terminated string to the Atari console.
; Parameters:
;   A0 - address of the string to display.
; Returns:
;   No value.
; Side effects:
;   Uses the operating-system console-write trap.
; ---------------------------------------------------------------------------
WriteConsoleString:    
             movem.l   d0-d2/a1,-(sp)
             movea.l   a0,a1
             clr.l     d0
CountLoop:   
             tst.b     (a1)
             beq.s     WriteIt
             addq.l    R #1,a1
             addq.l    R #1,d0
             bra.s     CountLoop
WriteIt:     
             move.l    a0,-(sp)
             move.l    d0,-(sp)
             move.w    R #1,-(sp)
             move.w    R #R $40,-(sp)
             trap      R #1
             lea       12(sp),sp
             movem.l   (sp)+,d0-d2/a1
             rts       

; ---------------------------------------------------------------------------
; StartTimer
; Purpose:
;   Read the current system tick count through the Atari timer service.
; Parameters:
;   None.
; Returns:
;   D0 - current timer tick count.
; Side effects:
;   Calls the timer service and its ReadClock callback.
; ---------------------------------------------------------------------------
StartTimer:  
             pea       ReadClock(pc)
             move.w    R #38,-(sp)
             trap      R #14
             addq.l    R #6,sp
             rts       

; ---------------------------------------------------------------------------
; ReadClock
; Purpose:
;   Supply the current system tick count to the timer service.
; Parameters:
;   None.
; Returns:
;   D0 - value of the system tick counter.
; Side effects:
;   Reads the operating system's tick-count location.
; ---------------------------------------------------------------------------
ReadClock:   
             move.l    R $4ba,d0
             rts       

; ---------------------------------------------------------------------------
; StopTimer
; Purpose:
;   Calculate and print elapsed timer ticks as a decimal value.
; Parameters:
;   D0 - start tick count returned earlier by StartTimer.
; Returns:
;   No value; writes the elapsed value and unit label to the console.
; Side effects:
;   Reads the current timer, formats the difference, and prints it.
; ---------------------------------------------------------------------------
StopTimer:   
             move.l    d0,-(sp)
             lea       TimeMsg(pc),a0
             bsr       WriteConsoleString
             bsr       StartTimer
             move.l    (sp)+,d1
             sub.l     d1,d0
             bsr       LongToAscii
             bsr       WriteConsoleString
             lea       SecondsMsg(pc),a0
             bsr       WriteConsoleString
             rts       

; ---------------------------------------------------------------------------
; StringLength
; Purpose:
;   Count bytes in a NUL-terminated string without including its terminator.
; Parameters:
;   A0 - address of the string.
; Returns:
;   D0 - number of non-NUL bytes.
; Side effects:
;   Does not modify the string; advances a temporary pointer.
; ---------------------------------------------------------------------------
StringLength:          
             movea.l   a0,a1
             clr.l     d0
SLLoop:      
             tst.b     (a1)
             beq.s     SLDone
             addq.l    R #1,a1
             addq.l    R #1,d0
             bra.s     SLLoop
SLDone:      
             rts       

; ---------------------------------------------------------------------------
; LongToAscii
; Purpose:
;   Convert a signed 32-bit integer to decimal text in the shared buffer.
; Parameters:
;   D0 - integer value to format.
; Returns:
;   A0 - address of the first character in ElapsedBuffer.
; Side effects:
;   Writes digits and an optional minus sign into ElapsedBuffer.
; ---------------------------------------------------------------------------
LongToAscii: 
             movem.l   d1-d6/a1,-(sp)
             lea       ElapsedBuffer+31,a1
             clr.b     (a1)
             moveq     R #0,d5
             tst.l     d0
             bne.s     CheckNegative
             subq.l    R #1,a1
             move.b    R #'0',(a1)
             movea.l   a1,a0
             movem.l   (sp)+,d1-d6/a1
             rts       

CheckNegative:         
             tst.l     d0
             bge.s     Convert
             moveq     R #1,d5
             neg.l     d0

Convert:     
ConvLoop:    
             moveq     R #0,d2
             moveq     R #0,d1
             moveq     R #31,d3
DivLoop:     
             lsl.l     R #1,d0
             addx.l    d1,d1
             lsl.l     R #1,d2
             cmpi.l    R #10,d1
             blt.s     DivNoSubtract
             subi.l    R #10,d1
             addq.l    R #1,d2
DivNoSubtract:         
             dbra      d3,DivLoop
             addi.b    R #'0',d1
             subq.l    R #1,a1
             move.b    d1,(a1)
             move.l    d2,d0
             tst.l     d0
             bne.s     ConvLoop
             tst.b     d5
             beq.s     FinishNum
             suba.l    R #1,a1
             move.b    R #'-',(a1)
FinishNum:   
             movea.l   a1,a0
             movem.l   (sp)+,d1-d6/a1
             rts       

             .DATA 
InputPath:   .DC.b "INPUT.TXT",0
OutputPath:  .DC.b "OUTPUT.TXT",0
ProgramName: .DC.b "======INTROSORT 68000 ASM=======",13,10,0
CompleteMsg: .DC.b "==========RUN COMPLETE==========",13,10,0
LoadingMsg:  .DC.b "READING INPUT FILE...",0
SavingMsg:   .DC.b "SAVING OUTPUT FILE...",0
SortingMsg:  .DC.b "SORTING ELEMENTS...",0
DoneMsg:     .DC.b "DONE.",13,10,0
TimeMsg:     .DC.b "INSTROSORT TOOK ",0
SecondsMsg:  .DC.b " SECONDS.",13,10,0
             .EVEN 
StartTime:   .DC.l 0
ParsedCount: .DC.l 0
BytesReadTracker:      .DC.l 0
		.BSS 
		.EVEN 
ArrayBuffer: 	.DS.l 1000
InputBuffer: 	.DS.b 32768
ElapsedBuffer:	.DS.b 32