$script:Intros = 0
$script:Inserts = 0
$script:Heaps = 0
# -------------------------------------------------------------------
# Read-File
# Purpose:
#   Read non-blank integer records from the named input file into the program collection or shared array.
# Parameters:
# FileSpec - input or output file path.
# Returns:
#   A PSCustomObject whose Values property contains the parsed integer list.
# Side effects:
#   Opens and closes the input file, populates the collection or shared array, and may update its element count.
# -------------------------------------------------------------------
function Read-File {
	param([string] $FileSpec)
	Write-Host "READING INPUT FILE..." -NoNewline
	$values = [Collections.Generic.List[int]]::new()
	foreach ($line in [IO.File]::ReadLines($FileSpec)) {
		if(-not [string]::ISNullOrWhiteSpace($line)) {
			$values.Add([int]::Parse($line))
		}
	}
	Write-Host "DONE."
	return [PSCustomObject]@{ Values = $values }
}

# -------------------------------------------------------------------
# Save-File
# Purpose:
#   Write the sorted integer collection or shared array to the named output file, one value per line.
# Parameters:
# Values - integer sequence to read, sort, or write; range operations modify it in place.
# FileSpec - input or output file path.
# Returns:
#   No value; writes the output file.
# Side effects:
#   Creates or replaces the output file and reports file progress.
# -------------------------------------------------------------------
function Save-File {
	param(
		[Collections.Generic.List[int]] $Values,
		[string] $FileSpec
	)
	Write-Host "WRITING OUTPUT FILE..." -NoNewline
	[IO.File]::WriteAllLines($FIleSpec, [string[]] $Values)
	Write-Host "DONE."
}

# -------------------------------------------------------------------
# Sift-Down
# Purpose:
#   Restore max-heap order below the specified root within the active heap range.
# Parameters:
# Values - integer sequence to read, sort, or write; range operations modify it in place.
# Root - current heap root index.
# Start - inclusive first index of the active range.
# End - exclusive end index of the active range.
# Returns:
#   No value; rearranges the range in place.
# Side effects:
#   Mutates the sequence and may stop once the heap property is restored.
# -------------------------------------------------------------------
function Sift-Down {
	param(
		[Collections.Generic.List[int]] $Values,
		[int] $Root,
		[int] $Start,
		[int] $End
	)
	while($Start + 2 * ($Root - $Start) + 1 -lt $End) {
		$child = $Start + 2 * ($Root - $Start) + 1;
		if($child + 1 -lt $End -and $Values[$child] -lt $Values[$child + 1]) {
			$child++
		}
		if($Values[$Root] -ge $Values[$child]) {
			return
		}
		$Values[$Root], $Values[$child] = $Values[$child], $Values[$Root]
		$Root = $child
	}
}

# -------------------------------------------------------------------
# Heap-Sort
# Purpose:
#   Sort the selected range in place with heapsort, the worst-case introsort fallback.
# Parameters:
# Values - integer sequence to read, sort, or write; range operations modify it in place.
# Start - inclusive first index of the active range.
# End - exclusive end index of the active range.
# Returns:
#   No value; sorts the selected range in place.
# Side effects:
#   Mutates the range and increments the heapsort counter where present.
# -------------------------------------------------------------------
function Heap-Sort {
	param(
		[Collections.Generic.List[int]] $Values,
		[int] $Start,
		[int] $End
	)
	$script:Heaps++
	for($root = $Start + [int](($End - $Start) / 2 - 1); $root -ge $Start; $root--) {
		Sift-Down -Values $Values -Root $root -Start $Start -End $End
	}
	for($last = $End -1; $last -gt $Start; $last--) {
		$Values[$Start], $Values[$last] = $Values[$last], $Values[$Start]
		Sift-Down -Values $Values -Root $Start -Start $Start -End $last
	}
}

# -------------------------------------------------------------------
# Insertion-Sort
# Purpose:
#   Sort the selected range in place with insertion sort, which is efficient for short ranges.
# Parameters:
# Values - integer sequence to read, sort, or write; range operations modify it in place.
# Start - inclusive first index of the active range.
# End - exclusive end index of the active range.
# Returns:
#   No value; sorts the selected range in place.
# Side effects:
#   Mutates the range and increments the insertion-sort counter where present.
# -------------------------------------------------------------------
function Insertion-Sort {
	param(
		[Collections.Generic.List[int]] $Values,
		[int] $Start,
		[int] $End
	)
	$script:Inserts++
	for($index = $Start; $index -lt $End; $index++) {
		$value = $Values[$index]
		$pos = $index - 1
		while($pos -ge $Start -and $Values[$pos] -gt $value) {
			$Values[$pos + 1] = $Values[$pos]
			$pos--
		}
		$Values[$pos + 1] = $value
	}
}

# -------------------------------------------------------------------
# Partition
# Purpose:
#   Partition the selected range around its middle-element pivot and return the first index of the right-hand range.
# Parameters:
# Values - integer sequence to read, sort, or write; range operations modify it in place.
# Start - inclusive first index of the active range.
# End - exclusive end index of the active range.
# Returns:
#   The first index of the right partition, which is also the left boundary of the recursive ranges.
# Side effects:
#   Reorders the range in place while inward scans keep each access inside the active bounds.
# -------------------------------------------------------------------
function Partition {
	param(
		[Collections.Generic.List[int]] $Values,
		[int] $Start,
		[int] $End
	)
	$left = $Start
	$right = $End - 1
	$pivot = $Values[$Start + ($End - $Start) / 2]
	while($left -le $Right) {
		while($Values[$left] -lt $pivot) {
			$left++
		}
		while($Values[$right] -gt $pivot) {
			$right--
		}
		if($left -le $right) {
			$Values[$left], $Values[$right] = $Values[$right], $Values[$left]
			$left++
			$right--
		}
	}
	return $left
}

# -------------------------------------------------------------------
# Intro-Sort
# Purpose:
#   Sort the selected range in place: insertion sort for short ranges, heapsort when the depth budget expires, otherwise partition and recurse.
# Parameters:
# Values - integer sequence to read, sort, or write; range operations modify it in place.
# Start - inclusive first index of the active range.
# End - exclusive end index of the active range.
# MaxDepth - remaining partition-depth budget before heapsort fallback.
# Returns:
#   No value; sorts the selected range in place.
# Side effects:
#   Mutates the range and updates the introsort counter; recursive calls reduce the depth budget.
# -------------------------------------------------------------------
function Intro-Sort {
	param(
		[Collections.Generic.List[int]] $Values,
		[int] $Start,
		[int] $End,
		[int] $MaxDepth
	)
	$script:Intros++
	$length = $End - $Start
	if($length -le 1) {
		return
	}
	if($length -lt 16) {
		Insertion-Sort -Values $Values -Start $Start -End $End
	}
	elseif ($MaxDepth -le 0) {
		Heap-Sort -Values $Values -Start $Start -End $End
	}
	else {
		$part = Partition -Values $Values -Start $Start -End $End
		Intro-Sort -Values $Values -Start $Start -End $part -MaxDepth ($MaxDepth - 1)
		Intro-Sort -Values $Values -Start $part -End $End -MaxDepth ($MaxDepth - 1)
	}
}

# -------------------------------------------------------------------
# Perform-Sort
# Purpose:
#   Choose the initial depth budget, time the top-level introsort, and report completion.
# Parameters:
# Values - integer sequence to read, sort, or write; range operations modify it in place.
# Returns:
#   Elapsed time measured by this implementation.
# Side effects:
#   Starts and stops a timer, prints progress, and invokes introsort on the full sequence.
# -------------------------------------------------------------------
function Perform-Sort {
	param(
		[Collections.Generic.List[int]] $Values
	)
	Write-Host "SORTING ELEMENT..." -NoNewline
	$timer = [System.Diagnostics.Stopwatch]::StartNew()
	$maxDepth = 0
	if($Values.Count -gt 1) {
		$maxDepth = [int][Math]::Log2($Values.Count) * 2 
	}
	Intro-Sort -Values $Values -Start 0 -End $Values.Count -MaxDepth $maxDepth
	$timer.Stop()
	Write-Host "DONE."
	return $timer.Elapsed.TotalSeconds
}

Write-Host "======INTROSORT POWERSHELL======"
$wrapper = Read-File "D:\Sorting\Sorting_Input.txt"
$values = $wrapper.Values
$elapsed = Perform-Sort -Values $values
Save-File $values "D:\Sorting\Output_PS.txt"
Write-Host "==========RUN COMPLETE=========="
Write-Host ("INTROSORT TOOK {0:F6} SECONDS." -f $elapsed)
Write-Host "================================"
Write-Host "SORT CALLED | TIMES"
Write-Host "------------+-------------------"
Write-Host ("Intro       | {0} " -f $script:Intros)
Write-Host ("Insertion    | {0} " -f $script:Inserts)
Write-Host ("Heap        | {0} " -f $script:Heaps)
Write-Host "================================"