$script:Intros = 0
$script:Inserts = 0
$script:Heaps = 0
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 }
}

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."
}

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
	}
}

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
	}
}

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
	}
}

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
}

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)
	}
}

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 "================================"