OPTION CASEMAP:NONE

GENERIC_READ            equ 80000000h
GENERIC_WRITE           equ 40000000h
FILE_SHARE_READ         equ 00000001h
FILE_SHARE_WRITE        equ 00000002h
CREATE_NEW              equ 1
CREATE_ALWAYS           equ 2
OPEN_EXISTING           equ 3
OPEN_ALWAYS             equ 4
TRUNCATE_EXISTING       equ 5
FILE_ATTRIBUTE_NORMAL   equ 00000080h
INVALID_HANDLE_VALUE    equ -1

; ---------------------------------------------------------------------------
; Data section
; ---------------------------------------------------------------------------
.data 
InputPath				BYTE "D:/Sorting/Sorting_Input.txt", 0
OutputPath				BYTE "D:/Sorting/Output_x64ASM.txt", 0
ProgramName				BYTE "=======INSTROSORT x64 ASM=======", 13, 10, 0
LoadingMessage			BYTE "READING INPUT FILE...", 0
SavingMessage			BYTE "SAVING OUTPUT FILE...", 0
SortingMessage			BYTE "SORTING ELEMENTS...", 0
DoneMessage				BYTE "DONE.", 13, 10, 0
CompleteMessage			BYTE "==========RUN COMPLETE==========", 13, 10, 0
TimeMessage				BYTE "INTROSORT TOOK ", 0
SecondsMessage			BYTE " SECONDS.", 10, 13, 0
IntroCountLabel         BYTE "INTRO       |", 0
InsertCountLabel        BYTE "INSERTION   |", 0
HeapCountLabel          BYTE "HEAP        |", 0
SortCountTitle			BYTE "SORT CALLED | TIMES", 13, 10, 0
SortCountRule			BYTE "------------+-------------------", 13, 10, 0
NewLine					BYTE 13, 10, 0

; High resolution timer storage and scaling factor
StartTime       QWORD 0
ms_factor       REAL8 1000.0
IntroCount      DWORD 0
InsertCount     DWORD 0
HeapCount       DWORD 0

; File read buffer and helper counters
InputBuffer     BYTE 32768 DUP(?)
BytesReadTracker DWORD 0         

.code 
PUBLIC HeapSort
PUBLIC IntroSort
PUBLIC IntroSortMain
PUBLIC SiftDown
PUBLIC InsertionSort
PUBLIC Partition
PUBLIC LoadFile
PUBLIC SaveFile
PUBLIC WriteConsoleString
PUBLIC LoadInput
PUBLIC SaveOutput
PUBLIC StartTimer
PUBLIC StopTimerAndWriteElapsed

EXTERN GetStdHandle:PROC
EXTERN WriteConsoleA:PROC
EXTERN CreateFileA:PROC
EXTERN ReadFile:PROC
EXTERN CloseHandle:PROC
EXTERN WriteFile:PROC
EXTERN QueryPerformanceCounter:PROC
EXTERN QueryPerformanceFrequency:PROC

; ---------------------------------------------------------------------------
; SaveOutput PROC
; Purpose:
;   Write an array of signed 32-bit integers, one per line, to a file.
;   Each integer is formatted as an ASCII decimal string with CRLF termination.
;
; Parameters (incoming registers):
;   rcx - pointer to first int32 element (int32*)
;   rdx - number of elements to write (count)
;   r8  - pointer to output filename (char*)
;
; Returns:
;   None (no valuable register return). Preserves non-volatile registers.
;
; Registers used (and meaning within the proc):
;   rbx - cursor into the integer array (kept non-volatile)
;   r12 - remaining element count (kept non-volatile)
;   r13..r15, rsi, rdi, r14 - scratch and stack buffer cursors for formatting
;   rax, rcx, rdx, r8, r9, ecx, edx - caller-saved temporaries for API calls and division
;   Stack layout used extensively for safe shadow-space and local string buffer.
;
; Notes:
;   - Preserves non-volatile registers by storing them on the stack at entry
;   - Uses a backward-building scratch buffer for number formatting to avoid heap allocations
; ---------------------------------------------------------------------------
SaveOutput PROC
    ; Allocate 144 bytes total frame. 8 (ret addr) + 144 = 152 bytes total (Perfect 16-byte alignment match)
    SUB     rsp, 152
    
    ; Protect non-volatile registers completely above our string writing buffer space
    MOV     QWORD PTR [rsp+80], rbx     
    MOV     QWORD PTR [rsp+88], rsi     
    MOV     QWORD PTR [rsp+96], rdi     
    MOV     QWORD PTR [rsp+104], r12     
    MOV     QWORD PTR [rsp+112], r13     
    MOV     QWORD PTR [rsp+120], r14    
    MOV     QWORD PTR [rsp+128], r15    

    MOV     rbx, rcx                    ; cursor into the value array
    MOV     r12, rdx                    ; remaining element count
    
    ; --- Open file ---
    MOV     rcx, r8                     ; lpFileName for CreateFileA
    MOV     rdx, GENERIC_WRITE   
    MOV     r8,  FILE_SHARE_READ 
    MOV     r9,  0                      ; lpSecurityAttributes (NULL)
    
    MOV     QWORD PTR [rsp+32], CREATE_ALWAYS
    MOV     QWORD PTR [rsp+40], FILE_ATTRIBUTE_NORMAL
    MOV     QWORD PTR [rsp+48], 0
    CALL    CreateFileA
    
    ; CORRECTION: Cache file handle cleanly at [rsp+136], completely safe from API shadow spaces
    MOV     QWORD PTR [rsp+136], rax     
    CMP     QWORD PTR [rsp+136], INVALID_HANDLE_VALUE
    JE      SaveDone             

WriteLoop:
    TEST    r12, r12
    JE      CloseOut
    
    LEA     r14, [rsp+78]               ; Start at the back end of our safe stack scratch space
    MOV     byte PTR [r14], 0Ah         ; Pre-fill LF
    DEC     r14
    MOV     byte PTR [r14], 0Dh         ; Pre-fill CR
    MOV     r9d, 2                      ; Clear length tracking counter immediately to 2 (CR + LF)

    MOV     eax, dword PTR [rbx]        ; current element value to format
    
    ; Check for zero
    TEST    eax, eax
    JNE     CheckNegative
    DEC     r14
    MOV     byte PTR [r14], '0'
    INC     r9d
    JMP     FinishNum

CheckNegative:
    ; Check if the value is negative
    XOR     r15d, r15d                  ; r15d = 0 means positive
    CMP     eax, 0
    JGE     Convert
    MOV     r15d, 1                     ; Mark as negative
    NEG     eax                         ; Convert negative number to positive for unsigned DIV math

Convert:
    MOV     ecx, 10                     ; divisor (base 10)
SaveNumberLoop:
    XOR     edx, edx
    DIV     ecx                         ; eax:edx / ecx -> eax = quotient, edx = remainder
    ADD     dl, '0'                     ; Convert digit to ASCII
    DEC     r14                         ; Move text cursor backward
    MOV     byte PTR [r14], dl
    INC     r9d                         ; Increment string length count safely via register math
    TEST    eax, eax
    JNE     SaveNumberLoop

    ; Append negative sign if original number was negative
    CMP     r15d, 1
    JNE     FinishNum
    DEC     r14
    MOV     byte PTR [r14], '-'         ; Append minus sign to text sequence
    INC     r9d

FinishNum:
    MOV     r8d, r9d                    ; 3rd arg: explicit character payload count limit

    MOV     rcx, QWORD PTR [rsp+136]    ; 1st arg: Load safe file handle from [rsp+136]
    MOV     rdx, r14                    ; 2nd arg: direct pointer to the start of our string data
    MOV     r9, 0                       ; 4th arg: lpNumberOfBytesWritten (NULL)
    MOV     QWORD PTR [rsp+32], 0       ; 5th arg: lpOverlapped -> shadow-safe at [rsp+32]
    CALL    WriteFile

    ADD     rbx, 4
    DEC     r12
    JMP     WriteLoop

CloseOut:
    MOV     rcx, QWORD PTR [rsp+136]
    CALL    CloseHandle
    
SaveDone:
    ; Restore non-volatile tracking states cleanly out of structural boundaries
    MOV     rbx, QWORD PTR [rsp+80]     
    MOV     rsi, QWORD PTR [rsp+88]     
    MOV     rdi, QWORD PTR [rsp+96]     
    MOV     r12, QWORD PTR [rsp+104]     
    MOV     r13, QWORD PTR [rsp+112]     
    MOV     r14, QWORD PTR [rsp+120]    
    MOV     r15, QWORD PTR [rsp+128]    
    ADD     rsp, 152
    RET
SaveOutput ENDP

; ---------------------------------------------------------------------------
; LoadInput PROC
; Purpose:
;   Open the file specified at r8, read up to 32KB into `InputBuffer`, parse
;   whitespace-separated decimal integers and store them into the array at rcx.
;   Parsing honors an optional leading minus sign.
;
; Parameters:
;   rcx - pointer to destination int32 array (int32*)
;   rdx - maximum number of elements to parse (count)
;   r8  - file path (char*)
;
; Returns:
;   rax - number of integers parsed (0 on error or no data)
;
; Registers used:
;   r13 - output array base (preserved across calls)
;   rbx - max element count (preserved across calls)
;   r10 - file handle (temporary, closed before parsing)
;   r11 - pointer to InputBuffer
;   r14 - read cursor pointer (pointer into InputBuffer)
;   r15d- remaining bytes / temp counters
;   r8d, r12d etc - temporary accumulators during parsing
;   Non-volatile rbx, rsi, rdi, r12..r15 are saved/restored on entry/exit.
; Notes:
;   - Protects non-volatile registers and uses a global InputBuffer so stack stays small.
;   - Stops parsing when the element count limit is reached.
; ---------------------------------------------------------------------------
LoadInput PROC
    SUB     rsp, 120
     
    ; Shifted tracking spills down by 8 bytes to match the new 112-byte layout
    MOV     QWORD PTR [rsp+56], rbx     
    MOV     QWORD PTR [rsp+64], rsi     
    MOV     QWORD PTR [rsp+72], rdi     
    MOV     QWORD PTR [rsp+80], r12     
    MOV     QWORD PTR [rsp+88], r13     
    MOV     QWORD PTR [rsp+96], r14    
    MOV     QWORD PTR [rsp+104], r15 

    SIZE_GUARD:
    CMP     rcx, 0
    JE      LoadDone  
    TEST    rdx, rdx
    JZ      LoadDone  

    MOV     r13, rcx                    ; r13 = output array base
    MOV     rbx, rdx                    ; rbx = max element count

    ; --- Open file ---
    MOV     rcx, r8                     ; 1st arg: lpFileName
    MOV     rdx, GENERIC_READ           ; 2nd arg: dwDesiredAccess
    MOV     r8, FILE_SHARE_READ         ; 3rd arg: dwShareMode
    MOV     r9, 0                       ; 4th arg: lpSecurityAttributes (NULL)
    
    ; Safe out-of-bounds stack argument placement
    MOV     QWORD PTR [rsp+32], OPEN_EXISTING       
    MOV     QWORD PTR [rsp+40], FILE_ATTRIBUTE_NORMAL 
    MOV     QWORD PTR [rsp+48], 0                   
    CALL    CreateFileA

    MOV     r10, rax                    ; r10 = file handle
    CMP     r10, INVALID_HANDLE_VALUE
    JE      LoadErrorExit               
    MOV     QWORD PTR [rsp+112], r10

    MOV     DWORD PTR [BytesReadTracker], 0

    ; --- Read into global buffer ---
    LEA     r11, InputBuffer            ; destination buffer
    MOV     r12d, 32768                 ; buffer capacity in bytes

    MOV     rcx, QWORD PTR [rsp+112]    ; 1st arg: hFile
    MOV     rdx, r11                    ; 2nd arg: lpBuffer
    MOV     r8d, r12d                   ; 3rd arg: bytes to read
    LEA     r9, OFFSET BytesReadTracker ; RIP-relative pointer
    MOV     QWORD PTR [rsp+32], 0       ; 5th arg: lpOverlapped (NULL)
    CALL    ReadFile

    TEST    eax, eax
    JZ      SafeCloseExit               

    MOV     rcx, QWORD PTR [rsp+112]
    CALL    CloseHandle
    JMP     StartParsing

SafeCloseExit:
    MOV     rcx, QWORD PTR [rsp+112]
    CALL    CloseHandle
    MOV     DWORD PTR [BytesReadTracker], 0

StartParsing:
    ; --- Parse ---
    MOV     rax, 0                      ; rax = running count of parsed integers
    LEA     r14, InputBuffer            ; r14 = tracking cursor position pointer
    MOV     r15d, DWORD PTR [BytesReadTracker]
    
    TEST    r15d, r15d                  
    JZ      LoadDone                    

ParseLoop:
    CMP     r15d, 0
    JE      LoadDone

SkipWS:
    CMP     byte PTR [r14], 0Dh
    JE      NextChar
    CMP     byte PTR [r14], 0Ah
    JE      NextChar
    CMP     byte PTR [r14], ' '
    JE      NextChar
    CMP     byte PTR [r14], 9
    JE      NextChar
    JMP     ParseNum

NextChar:
    INC     r14
    DEC     r15d
    JMP     ParseLoop

ParseNum:
    XOR     r8d, r8d                    ; Clear the digit accumulator
    XOR     r12d, r12d                  ; r12d = 0 means positive, 1 means negative

    ; Check if the very first character of the number is a minus sign
    CMP     byte PTR [r14], '-'
    JNE     DigitLoop                   ; If not, skip to parsing digits normally
    MOV     r12d, 1                     ; Mark the number as negative
    INC     r14                         ; Skip over the minus sign in the buffer
    DEC     r15d                        ; Decrement remaining buffer bytes counter
    JZ      LoadDone                    ; If file ends abruptly on a minus sign, exit

DigitLoop:
    CMP     r15d, 0
    JE      CheckSignAndStore
    MOV     dl, byte PTR [r14]          
    CMP     dl, '0'
    JB      CheckSignAndStore           
    CMP     dl, '9'
    JA      CheckSignAndStore           
    SUB     dl, '0'                     
    IMUL    r8d, r8d, 10
    ADD     r8d, edx
    INC     r14
    DEC     r15d
    JMP     DigitLoop

CheckSignAndStore:
    ; Apply the negative sign if our sign flag was set
    CMP     r12d, 1
    JNE     StoreNum
    NEG     r8d                         ; Negate the accumulated 32-bit integer value

StoreNum:
    MOV     dword PTR [r13 + rax*4], r8d
    INC     rax
    CMP     rax, rbx                    ; Check if we hit the maximum element count limit
    JAE     LoadDone                    ; If we are full, exit parsing completely

    ; Advance the buffer cursor past the trailing character we just hit
    INC     r14                         ; Move pointer forward by 1 character
    DEC     r15d                        ; Decrease remaining byte counter by 1
    JMP     ParseLoop                   ; Go process the next integer freshly

LoadErrorExit:
    XOR     rax, rax                    

LoadDone:
    ; Restore non-volatile registers from their updated slots
    MOV     rbx, QWORD PTR [rsp+56]     
    MOV     rsi, QWORD PTR [rsp+64]     
    MOV     rdi, QWORD PTR [rsp+72]     
    MOV     r12, QWORD PTR [rsp+80]     
    MOV     r13, QWORD PTR [rsp+88]     
    MOV     r14, QWORD PTR [rsp+96]     
    MOV     r15, QWORD PTR [rsp+104]    
    ADD     rsp, 120
    RET
LoadInput ENDP

; ---------------------------------------------------------------------------
; LoadFile PROC
; Purpose:
;   Wrapper that prints the loading message and calls LoadInput.
;
; Parameters:
;   rcx - destination array pointer (forwarded to LoadInput)
;   rdx - max element count (forwarded to LoadInput)
;
; Returns:
;   rax - number of parsed integers returned by LoadInput
;
; Registers used:
;   rbx, rsi - saved/restored around calls; used to cache incoming arguments
; ---------------------------------------------------------------------------
LoadFile PROC
    SUB     rsp, 56
    MOV     QWORD PTR [rsp+32], rbx     ; Save rbx safely in shadow spill area
    MOV     QWORD PTR [rsp+40], rsi     ; Save rsi safely
    
    MOV     rbx, rcx                    ; Cache array base
    MOV     rsi, rdx                    ; Cache max count

    LEA     rcx, LoadingMessage
    CALL    WriteConsoleString

    MOV     rcx, rbx                    
    MOV     rdx, rsi                    
    MOV     r8, OFFSET InputPath
    CALL    LoadInput
    MOV     rsi, rax                    ; Preserve actual number of values read

    LEA     rcx, DoneMessage
    CALL    WriteConsoleString
    MOV     rax, rsi
    
    MOV     rbx, QWORD PTR [rsp+32]     ; Restore rbx
    MOV     rsi, QWORD PTR [rsp+40]     ; Restore rsi
    ADD     rsp, 56
    RET
LoadFile ENDP

; ---------------------------------------------------------------------------
; SaveFile PROC
; Purpose:
;   Wrapper that prints the saving message and calls SaveOutput.
;
; Parameters:
;   rcx - pointer to array to save (int32*)
;   rdx - number of elements to save
;
; Returns:
;   None
;
; Registers used:
;   rbx, rsi - saved/restored and used to forward args to SaveOutput
; ---------------------------------------------------------------------------
SaveFile PROC
    SUB     rsp, 56
    MOV     QWORD PTR [rsp+32], rbx     
    MOV     QWORD PTR [rsp+40], rsi     
     
    MOV     rbx, rcx                    ; Cache array base
    MOV     rsi, rdx                    ; Cache element count

    LEA     rcx, SavingMessage
    CALL    WriteConsoleString

    MOV     rcx, rbx                    
    MOV     rdx, rsi                    
    MOV     r8, OFFSET OutputPath       
    CALL    SaveOutput

    LEA     rcx, DoneMessage
    CALL    WriteConsoleString
    
    MOV     rbx, QWORD PTR [rsp+32]     ; Restore rbx
    MOV     rsi, QWORD PTR [rsp+40]     ; Restore rsi
    ADD     rsp, 56
    RET
SaveFile ENDP

; ---------------------------------------------------------------------------
; IntroSortMain PROC
; Purpose:
;   Top-level entry that prints program header, loads input, sorts, saves output,
;   and prints completion. This is the intended entry for external callers.
;
; Parameters:
;   rcx - pointer to array buffer (int32*)
;   rdx - maximum element count
;
; Returns:
;   None
;
; Stack/frame behaviour:
;   Uses RBP as frame anchor and aligns RSP to 16 bytes. Incoming parameters
;   are saved into stack home slots so they survive nested calls.
; ---------------------------------------------------------------------------
IntroSortMain PROC
    ; Establish standard, pristine stack frame tracking using RBP
    PUSH    rbp                         ; Save parent RBP frame anchor
    MOV     rbp, rsp                    ; RBP now points to our untouchable entry baseline
    
    AND     rsp, -16                    ; Safely mask RSP down to 16-byte alignment
    SUB     rsp, 64                     ; Shadow space plus array, capacity, count, and depth slots

    ; Save incoming call parameters directly into our aligned home spill spaces
    MOV     QWORD PTR [rsp+32], rcx     ; Save array base parameter
    MOV     QWORD PTR [rsp+40], rdx     ; Save max element count parameter

    LEA     rcx, ProgramName
    CALL    WriteConsoleString
    
    MOV     rcx, QWORD PTR [rsp+32]     ; Restore array base parameter
    MOV     rdx, QWORD PTR [rsp+40]     ; Restore max element count parameter
    CALL    LoadFile
    
    MOV     rcx, QWORD PTR [rsp+32]
    MOV     QWORD PTR [rsp+48], rax     ; Save actual number of values read
    MOV     eax, DWORD PTR [rsp+48]
    XOR     r10d, r10d
    CMP     eax, 1
    JBE     DepthReady
DepthLoop:
    SHR     eax, 1
    INC     r10d
    TEST    eax, eax
    JNE     DepthLoop
    SHL     r10d, 1
DepthReady:
    MOV     DWORD PTR [rsp+56], r10d

    LEA     rcx, SortingMessage
    CALL    WriteConsoleString

    CALL    StartTimer
    MOV     QWORD PTR [StartTime], rax

    MOV     rcx, QWORD PTR [rsp+32]
    XOR     edx, edx
    MOV     r8d, DWORD PTR [rsp+48]
    MOV     r9d, DWORD PTR [rsp+56]
    CALL    IntroSort

    LEA     rcx, DoneMessage
    CALL    WriteConsoleString
    LEA     rcx, TimeMessage
    CALL    WriteConsoleString
    MOV     rcx, QWORD PTR [StartTime]
    CALL    StopTimerAndWriteElapsed
    LEA     rcx, SecondsMessage
    CALL    WriteConsoleString

    LEA     rcx, SortCountTitle
    CALL    WriteConsoleString
    LEA     rcx, SortCountRule
    CALL    WriteConsoleString
    LEA     rcx, IntroCountLabel
    CALL    WriteConsoleString
    MOV     ecx, DWORD PTR [IntroCount]
    CALL    PrintUnsigned
    LEA     rcx, NewLine
    CALL    WriteConsoleString
    LEA     rcx, InsertCountLabel
    CALL    WriteConsoleString
    MOV     ecx, DWORD PTR [InsertCount]
    CALL    PrintUnsigned
    LEA     rcx, NewLine
    CALL    WriteConsoleString
    LEA     rcx, HeapCountLabel
    CALL    WriteConsoleString
    MOV     ecx, DWORD PTR [HeapCount]
    CALL    PrintUnsigned
    LEA     rcx, NewLine
    CALL    WriteConsoleString
    
    MOV     rcx, QWORD PTR [rsp+32]
    MOV     rdx, QWORD PTR [rsp+48]
    CALL    SaveFile
    
    LEA     rcx, CompleteMessage
    CALL    WriteConsoleString

    ; Cleanup and Restore Sequence
    MOV     rsp, rbp                    ; Snap RSP back to our un-clobberable entry state
    POP     rbp                         ; Restore parent frame pointer
    RET
IntroSortMain ENDP

; ---------------------------------------------------------------------------
; WriteConsoleString PROC
; Purpose:
;   Writes a null-terminated ASCII string at rcx to the console (STDOUT).
;
; Parameters:
;   rcx - pointer to NUL-terminated ASCII string
;
; Returns:
;   None
;
; Registers used:
;   r8  - local copy of rcx (string pointer)
;   r9  - console handle (returned by GetStdHandle)
;   r10d- counted length during scanning
;   rcx, rdx, r8d - used for WriteConsoleA arguments
;
; Notes:
;   - Leaves non-volatile registers unchanged (uses caller-saved registers only).
; ---------------------------------------------------------------------------
WriteConsoleString PROC
    SUB     rsp, 40                     ; Padded shadow space to keep stack 16-byte aligned
    MOV     QWORD PTR [rsp+32], rcx
    MOV     rcx, -11                    
    CALL    GetStdHandle
    MOV     r9, rax                     
    MOV     r8, QWORD PTR [rsp+32]
    MOV     rdx, r8                     
    XOR     r10d, r10d                  
CountLoop:
    CMP     byte PTR [rdx], 0
    JE      WriteIt
    INC     rdx
    INC     r10d
    JMP     CountLoop
WriteIt:
    MOV     rcx, r9                     
    MOV     rdx, r8                     
    MOV     r8d, r10d                   
    XOR     r9, r9                       
    XOR     r10, r10
    MOV     QWORD PTR [rsp+32], 0
    CALL    WriteConsoleA
    ADD     rsp, 40
    RET
WriteConsoleString ENDP

; ---------------------------------------------------------------------------
; PrintUnsigned PROC
;   Write the unsigned integer in ecx to the console.
; ---------------------------------------------------------------------------
PrintUnsigned PROC
    SUB     rsp, 56
    LEA     r10, [rsp+47]
    MOV     BYTE PTR [r10], 0
    TEST    ecx, ecx
    JNZ     PrintUnsignedConvert
    DEC     r10
    MOV     BYTE PTR [r10], '0'
    JMP     PrintUnsignedWrite
PrintUnsignedConvert:
    MOV     eax, ecx
PrintUnsignedLoop:
    XOR     edx, edx
    MOV     r11d, 10
    DIV     r11d
    ADD     dl, '0'
    DEC     r10
    MOV     BYTE PTR [r10], dl
    TEST    eax, eax
    JNZ     PrintUnsignedLoop
PrintUnsignedWrite:
    MOV     rcx, r10
    CALL    WriteConsoleString
    ADD     rsp, 56
    RET
PrintUnsigned ENDP

; ---------------------------------------------------------------------------
; SiftDown PROC
;   Restore the max-heap property for a root in [start, end).
;   rcx=array, edx=root, r8d=start, r9d=end.
; ---------------------------------------------------------------------------
SiftDown PROC
SiftLoop:
    MOV     r10d, edx
    SUB     r10d, r8d
    SHL     r10d, 1
    INC     r10d
    ADD     r10d, r8d
    CMP     r10d, r9d
    JAE     SiftDone

    MOV     r11d, r10d
    INC     r11d
    CMP     r11d, r9d
    JAE     SiftCompareRoot
    MOV     eax, DWORD PTR [rcx+r10*4]
    CMP     eax, DWORD PTR [rcx+r11*4]
    JGE     SiftCompareRoot
    MOV     r10d, r11d

SiftCompareRoot:
    MOV     eax, DWORD PTR [rcx+rdx*4]
    CMP     eax, DWORD PTR [rcx+r10*4]
    JGE     SiftDone
    MOV     r11d, DWORD PTR [rcx+r10*4]
    MOV     DWORD PTR [rcx+r10*4], eax
    MOV     DWORD PTR [rcx+rdx*4], r11d
    MOV     edx, r10d
    JMP     SiftLoop
SiftDone:
    RET
SiftDown ENDP

; ---------------------------------------------------------------------------
; HeapSort PROC
;   In-place heapsort of the half-open range [start, end).
;   rcx=array, edx=start, r8d=end.
; ---------------------------------------------------------------------------
HeapSort PROC
    PUSH    rbx
    PUSH    rsi
    PUSH    rdi
    PUSH    r12
    SUB     rsp, 40

    MOV     rbx, rcx
    MOV     r12d, edx
    MOV     edi, r8d
    INC     DWORD PTR [HeapCount]

    MOV     esi, edi
    SUB     esi, r12d
    CMP     esi, 1
    JBE     HeapDone
    SHR     esi, 1
    ADD     esi, r12d
    DEC     esi
HeapBuild:
    MOV     rcx, rbx
    MOV     edx, esi
    MOV     r8d, r12d
    MOV     r9d, edi
    CALL    SiftDown
    DEC     esi
    CMP     esi, r12d
    JGE     HeapBuild

    MOV     esi, edi
    DEC     esi
HeapExtract:
    CMP     esi, r12d
    JLE     HeapDone
    MOV     eax, DWORD PTR [rbx+r12*4]
    MOV     r10d, DWORD PTR [rbx+rsi*4]
    MOV     DWORD PTR [rbx+r12*4], r10d
    MOV     DWORD PTR [rbx+rsi*4], eax
    MOV     rcx, rbx
    MOV     edx, r12d
    MOV     r8d, r12d
    MOV     r9d, esi
    CALL    SiftDown
    DEC     esi
    JMP     HeapExtract

HeapDone:
    ADD     rsp, 40
    POP     r12
    POP     rdi
    POP     rsi
    POP     rbx
    RET
HeapSort ENDP

; ---------------------------------------------------------------------------
; InsertionSort PROC
;   In-place insertion sort of the half-open range [start, end).
;   rcx=array, edx=start, r8d=end.
; ---------------------------------------------------------------------------
InsertionSort PROC
    PUSH    rbx
    PUSH    r12
    PUSH    r13
    PUSH    r14
    PUSH    r15

    MOV     rbx, rcx
    MOV     r12d, edx
    MOV     r13d, r8d
    INC     DWORD PTR [InsertCount]
    MOV     r14d, r12d
    INC     r14d
InsertionLoop:
    CMP     r14d, r13d
    JAE     InsertionDone
    MOV     r10d, DWORD PTR [rbx+r14*4]
    MOV     r15d, r14d
    DEC     r15d
InsertionShift:
    CMP     r15d, r12d
    JL      InsertionStore
    MOV     eax, DWORD PTR [rbx+r15*4]
    CMP     eax, r10d
    JLE     InsertionStore
    MOV     r11d, r15d
    INC     r11d
    MOV     DWORD PTR [rbx+r11*4], eax
    DEC     r15d
    JMP     InsertionShift
InsertionStore:
    MOV     r11d, r15d
    INC     r11d
    MOV     DWORD PTR [rbx+r11*4], r10d
    INC     r14d
    JMP     InsertionLoop
InsertionDone:
    POP     r15
    POP     r14
    POP     r13
    POP     r12
    POP     rbx
    RET
InsertionSort ENDP

; ---------------------------------------------------------------------------
; Partition PROC
;   Hoare partition of [start, end]; returns the split index in eax.
;   rcx=array, edx=start, r8d=end.
; ---------------------------------------------------------------------------
Partition PROC
    PUSH    rbx
    PUSH    r12
    PUSH    r13
    PUSH    r14
    PUSH    r15

    MOV     rbx, rcx
    MOV     r12d, edx
    MOV     r13d, r8d
    DEC     r13d
    MOV     eax, r8d
    SUB     eax, edx
    SHR     eax, 1
    ADD     eax, edx
    MOV     r14d, DWORD PTR [rbx+rax*4]
PartitionLoop:
    CMP     r12d, r13d
    JG      PartitionDone
PartitionLeft:
    CMP     r12d, r13d
    JG      PartitionDone
    MOV     eax, DWORD PTR [rbx+r12*4]
    CMP     eax, r14d
    JGE     PartitionRight
    INC     r12d
    JMP     PartitionLeft
PartitionRight:
    CMP     r13d, r12d
    JL      PartitionDone
    MOV     eax, DWORD PTR [rbx+r13*4]
    CMP     eax, r14d
    JLE     PartitionSwap
    DEC     r13d
    JMP     PartitionRight
PartitionSwap:
    MOV     eax, DWORD PTR [rbx+r12*4]
    MOV     r15d, DWORD PTR [rbx+r13*4]
    MOV     DWORD PTR [rbx+r12*4], r15d
    MOV     DWORD PTR [rbx+r13*4], eax
    INC     r12d
    DEC     r13d
    JMP     PartitionLoop
PartitionDone:
    MOV     eax, r12d
    POP     r15
    POP     r14
    POP     r13
    POP     r12
    POP     rbx
    RET
Partition ENDP

; ---------------------------------------------------------------------------
; IntroSort PROC
;   Sort [start, end] with a depth limit; uses insertion sort below 16 items
;   and heapsort when depth reaches zero.
;   rcx=array, edx=start, r8d=end, r9d=max depth.
; ---------------------------------------------------------------------------
IntroSort PROC
    PUSH    rbx
    PUSH    rsi
    PUSH    rdi
    PUSH    r12
    PUSH    r13
    PUSH    r14
    PUSH    r15
    SUB     rsp, 64

    MOV     QWORD PTR [rsp+32], rcx
    MOV     DWORD PTR [rsp+40], edx
    MOV     DWORD PTR [rsp+44], r8d
    MOV     DWORD PTR [rsp+48], r9d
    INC     DWORD PTR [IntroCount]

    MOV     eax, r8d
    SUB     eax, edx
    CMP     eax, 1
    JLE     IntroDone
    CMP     eax, 16
    JL      IntroUseInsertion
    TEST    r9d, r9d
    JLE     IntroUseHeap

    MOV     rcx, QWORD PTR [rsp+32]
    MOV     edx, DWORD PTR [rsp+40]
    MOV     r8d, DWORD PTR [rsp+44]
    CALL    Partition
    MOV     DWORD PTR [rsp+52], eax

    MOV     rcx, QWORD PTR [rsp+32]
    MOV     edx, DWORD PTR [rsp+40]
    MOV     r8d, DWORD PTR [rsp+52]
    MOV     r9d, DWORD PTR [rsp+48]
    DEC     r9d
    CALL    IntroSort

    MOV     rcx, QWORD PTR [rsp+32]
    MOV     edx, DWORD PTR [rsp+52]
    MOV     r8d, DWORD PTR [rsp+44]
    MOV     r9d, DWORD PTR [rsp+48]
    DEC     r9d
    CALL    IntroSort
    JMP     IntroDone

IntroUseInsertion:
    MOV     rcx, QWORD PTR [rsp+32]
    MOV     edx, DWORD PTR [rsp+40]
    MOV     r8d, DWORD PTR [rsp+44]
    CALL    InsertionSort
    JMP     IntroDone

IntroUseHeap:
    MOV     rcx, QWORD PTR [rsp+32]
    MOV     edx, DWORD PTR [rsp+40]
    MOV     r8d, DWORD PTR [rsp+44]
    CALL    HeapSort

IntroDone:
    ADD     rsp, 64
    POP     r15
    POP     r14
    POP     r13
    POP     r12
    POP     rdi
    POP     rsi
    POP     rbx
    RET
IntroSort ENDP

; ---------------------------------------------------------------------------
; StartTimer PROC
; Purpose:
;   Read the high-resolution performance counter and return its value in RAX.
;
; Parameters:
;   none (call directly)
;
; Returns:
;   rax - counter ticks at the moment of call
;
; Registers used:
;   uses QueryPerformanceCounter which writes a 64-bit value to the memory pointer
;   provided in rcx. This routine provides [rsp+32] as temporary storage.
; ---------------------------------------------------------------------------
StartTimer PROC
    SUB     rsp, 56                         ; Keep stack aligned before QueryPerformanceCounter
    LEA     rcx, [rsp+32]                   ; Safe home spill address allocation
    CALL    QueryPerformanceCounter
    MOV     rax, QWORD PTR [rsp+32]         ; Pull raw baseline ticks out cleanly
    ADD     rsp, 56
    RET
StartTimer ENDP

; ---------------------------------------------------------------------------
; StopTimerAndWriteElapsed PROC
; Purpose:
;   Compute elapsed time between the StartTime passed in RCX and the current
;   high resolution counter, convert to fractional seconds (nanosecond precision
;   scaled to seconds) and print the decimal string to console.
;
; Parameters:
;   rcx - StartTime ticks value (64-bit) previously saved by StartTimer/HeapSort
;
; Behavior / Registers:
;   rbx - used to save/restore a non-volatile register
;   rax - used for intermediate tick arithmetic (elapsed)
;   rsp scratch bytes used for QueryPerformanceCounter/Frequency outputs and string buffer
;   r12, r13, r15 used as temporary pointers/counters for string building
;
; Notes:
;   - Produces a decimal string with at least 9 fractional digits (nanosecond-like precision)
;   - Restores non-volatile rbx prior to return.
; Returns:
;   None; writes the formatted duration to the console.
; ---------------------------------------------------------------------------
StopTimerAndWriteElapsed PROC
    SUB     rsp, 152
    MOV     QWORD PTR [rsp+88], rbx         
    MOV     QWORD PTR [rsp+96], rsi
    MOV     QWORD PTR [rsp+104], rdi
    MOV     QWORD PTR [rsp+112], r12
    MOV     QWORD PTR [rsp+120], r13
    MOV     QWORD PTR [rsp+128], r15

    MOV     rbx, rcx                        ; rbx = StartTime ticks value passed from HeapSort

    LEA     rcx, [rsp+64]                   
    CALL    QueryPerformanceCounter
    MOV     rax, QWORD PTR [rsp+64]         ; rax = EndTime ticks value 

    SUB     rax, rbx                        ; rax = Raw Elapsed Clock Ticks

    ; --- ULTRA HIGH PRECISION INT MATH ---
    ; Multiply elapsed ticks by 1,000,000,000 to scale up to nanoseconds resolution
    IMUL    rax, rax, 1000000000

    ; Fetch the precise system hardware clock frequency
    LEA     rcx, [rsp+72]                   
    CALL    QueryPerformanceFrequency
    MOV     rcx, QWORD PTR [rsp+72]         ; rcx = Frequency ticks per second

    ; Divide (Ticks * 1,000,000,000) by Frequency to get Nanoseconds
    XOR     rdx, rdx                        ; Clear RDX for 64-bit division
    DIV     rcx                             ; rax = (Ticks * 1,000,000,000) / Frequency
    
    ; Setup safe forward scratch string mapping at [rsp+32]
    LEA     r13, [rsp+32]                   
    MOV     r12, r13                        
    XOR     r15d, r15d                      ; r15d = loop character digit counter

ElapsedDigitLoop:
    XOR     edx, edx                        ; Clear EDX inside the loop to prevent overflows
    MOV     ecx, 10
    DIV     ecx                             ; Divides edx:eax cleanly by 10
    ADD     dl, '0'
    MOV     byte PTR [r12], dl              ; Store character forward
    INC     r12
    INC     r15d
    
    ; We force the loop to extract AT LEAST 9 fractional decimal digits for nanoseconds
    CMP     r15d, 9
    JB      ElapsedDigitLoop
    TEST    eax, eax
    JNE     ElapsedDigitLoop

    ; Inject the manual decimal point and a leading '0'
    MOV     byte PTR [r12], '.'
    INC     r12
    MOV     byte PTR [r12], '0'
    INC     r12

    ; Symmetrical string reversal tracking block
    MOV     byte PTR [r12], 0               ; Append true string null-terminator
    MOV     rsi, r13                        
    MOV     rdi, r12                        
RevLoop:
    DEC     rdi
    CMP     rsi, rdi
    JAE     PrintTime
    MOV     al, byte PTR [rsi]
    MOV     dl, byte PTR [rdi]
    MOV     byte PTR [rsi], dl
    MOV     byte PTR [rdi], al
    INC     rsi
    JMP     RevLoop

PrintTime:
    MOV     byte PTR [r12], 0               ; Force strict terminal termination
    MOV     rcx, r13                        ; Pass direct pointer to string data payload
    CALL    WriteConsoleString
    
    MOV     rbx, QWORD PTR [rsp+88]         ; Restore loop anchors
    MOV     rsi, QWORD PTR [rsp+96]
    MOV     rdi, QWORD PTR [rsp+104]
    MOV     r12, QWORD PTR [rsp+112]
    MOV     r13, QWORD PTR [rsp+120]
    MOV     r15, QWORD PTR [rsp+128]
    ADD     rsp, 152
    RET
StopTimerAndWriteElapsed ENDP

END