#include <Array.au3>

Opt( "MustDeclareVars", 1 )

Global Const $hKernel32Dll = DllOpen( "kernel32.dll" )

Example( 1000, 3 )


Func Example( $iRows, $iCols )
	Local $aItems[$iRows][$iCols]

	; Fill array
	FillArray( $aItems )
	_ArrayDisplay( $aItems, "Unsorted" )

	; Sort array
	Local $tIndex = DllStructCreate( "uint[" & $iRows & "]" )
	Local $pIndex = DllStructGetPtr( $tIndex )
	Local $aCmps[3][3] = [ _
		[ 0, 1, +1 ], _ ; Col 0: Compared as strings, asc
		[ 1, 0, +1 ], _ ; Col 1: Compared as numbers, asc
		[ 2, 0, +1 ] ]  ; Col 2: Compared as numbers, asc
	SortArray( $aItems, $pIndex, $tIndex, $aCmps )

	; Display rows
	Local $iRows2 = $iRows, $j
	Local $aItems2[$iRows2][$iCols]
	For $i = 0 To $iRows2 - 1
		$j = DllStructGetData($tIndex,1,$i+1)
		For $k = 0 To $iCols - 1
			$aItems2[$i][$k] = $aItems[$j][$k]
		Next
	Next
	_ArrayDisplay( $aItems2, "Sorted" )
EndFunc

DllClose( $hKernel32Dll )

Func FillArray( ByRef $aItems )
	Local $aLetters[26] = [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', _
	                        'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' ]
	Local $s, $t, $iRows = UBound( $aItems )
	For $i = 0 To $iRows - 1
		$s = $aLetters[Random(0,25,1)]
		For $j = 1 To 9
			$s &= $aLetters[Random(0,25,1)]
		Next
		$aItems[$i][0] = $s                                                ; String
		$aItems[$i][1] = Random( 0, $iRows - 1, 1 )                        ; Integer
		$aItems[$i][2] = Random( 0, $iRows - 1, 1 ) + Round( Random(), 4 ) ; Float
		; Duplicate strings
		For $j = 1 To Random(0,2,1)
			If $i = $iRows - 1 Then ExitLoop
			$i += 1
			$aItems[$i][0] = $s                                                ; String
			$aItems[$i][1] = Random( 0, $iRows - 1, 1 )                        ; Integer
			$aItems[$i][2] = Random( 0, $iRows - 1, 1 ) + Round( Random(), 4 ) ; Float
			$t = $aItems[$i][1]
			; Duplicate strings and integers
			For $m = 1 To Random(0,2,1)
				If $i = $iRows - 1 Then ExitLoop
				$i += 1
				$aItems[$i][0] = $s                                                ; String
				$aItems[$i][1] = $t                                                ; Integer
				$aItems[$i][2] = Random( 0, $iRows - 1, 1 ) + Round( Random(), 4 ) ; Float
			Next
		Next
	Next
EndFunc

Func SortArray( ByRef $aItems, $pIndex, $tIndex, $aCmps )
	Local $iCmps = UBound( $aCmps ), $c, $r, $v[$iCmps]
	Local $lo, $hi, $mi
	For $i = 0 To UBound( $aItems ) - 1
		For $j = 0 To $iCmps - 1
			$v[$j] = $aItems[$i][$aCmps[$j][0]] ; Values
		Next
		$lo = 0
		$hi = $i - 1
		While $lo <= $hi ; Binary search
			$r = 0 ; Compare result (-1,0,1)
			$j = 0 ; Index in $aCmps array
			$mi = Int( ( $lo + $hi ) / 2 )
			While Not $r And $j < $iCmps                    ; This While-loop handles sorting by multiple
				$c = $aCmps[$j][0]   ; Column                 ; columns. Column values of the two rows are
				Switch $aCmps[$j][1] ; Number/string          ; compared until a difference is found.
					Case 0 ; Compare column values as numbers. The following line is an implementation of the spaceship or three-way comparison operator for numbers like StringCompare is for strings.
						$r = ( $v[$j] < $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ? -1 : $v[$j] = $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ? 0 : 1 ) * $aCmps[$j][2] ; * $iCmpAsc
					Case 1 ; Compare column values as strings. StringCompare is a spaceship or three-way comparison operator for strings.
						$r = StringCompare( $v[$j], $aItems[DllStructGetData($tIndex,1,$mi+1)][$c] ) * $aCmps[$j][2] ; * $iCmpAsc
				EndSwitch
				$j += 1
			WEnd
			Switch $r
				Case -1
					$hi = $mi - 1
				Case  1
					$lo = $mi + 1
				Case  0 ; Equal
					ExitLoop
			EndSwitch
		WEnd
		If $i > $mi Then _ ; Make space for the row number in index
			DllCall( $hKernel32Dll, "none", "RtlMoveMemory", "struct*", $pIndex+($mi+1)*4, "struct*", $pIndex+$mi*4, "ulong_ptr", ($i-$mi)*4 )
		DllStructSetData( $tIndex, 1, $i, $mi+1+($lo=$mi+1) ) ; Insert row number $i at position $mi+1+($lo=$mi+1) in index
	Next
EndFunc