Optimized _ArraySort

czardas · May 10, 2016

I have this funny habit of inventing things that have already been invented. :rolleyes:

Some internal functions could be renamed eg. __ArrayTagSort2D(), Here's a first redraft of the help file description. I've only included sections where changes would be required. What do you think?

Description:
Sort a 1D or 2D array on a specific index using the dualpivotsort/quicksort/insertionsort/tagsort algorithms

Syntax:
_ArraySort ( ByRef $aArray [, $iDescending = 0 [, $iStart = 0 [, $iEnd = 0 [, $iSubItem = 0 [, $iAlgorithm = 0]]]]] )

Parameters:
$iAlgorithm - [optional] Use dual-pivot sort for 1D arrays, or tag sort for 2D arrays (default = quicksort)

Comments:
By default the UDF uses a QuickSort algorithm to sort the array. Setting the $iAlgorithm parameter uses dual-pivot sort with 1D arrays, and tag sort with 2D arrays. Dual-pivot sort can be significantly faster for large arrays (> 50 elements) and tag sort can be significantly faster for arrays with a large number of columns. The tag sort method uses more memory and may be less suitable for sorting large arrays on a less powerful machine (depends on the amount of bloat).

With tag sort and 1D algorithms, relatively short arrays will be sorted using an insertion sort (< 15 elements/rows with Quick Sort and Tag Sort; < 45 elements with Dual-Pivot Sort). Note that there is no guarantee that a specific algorithm will be faster in any given case.

Needs Removing:
@error = 6 - $iPivot used with 2D array

Edited May 10, 2016 by czardas
grammar

Melba23 · May 10, 2016

czardas,

Great minds.....

Here is the suggested Help file text I have been working in this morning:

$iAlternate [optional]  1D array sorted with PivotSort algorithm
            2D array sorted with TagSort algorithm
            Default: both sorted with QuickSort algorithm

Return Value
Success: 1. 
Failure: 0 and sets the @error flag to non-zero. 
@error:  1 - $aArray is not an array
2 - $iStart is greater than $iEnd
3 - $iSubItem is greater than subitem count
4 - $aArray is not a 1D or 2D array
5 - $aArray is empty
6 - Deprecated

Remarks
By default the UDF uses a QuickSort algorithm to sort both 1D and 2D arrays.

For 1D arrays setting the $iAlternate parameter uses a DualPivotSort algorithm - this can be significantly faster for large arrays (> 50 elements). In both algorithms, relatively short arrays will be sorted using an insertion sort (< 15 elements with QuickSort; < 45 elements with Dual PivotSort).

For 2D arrays setting the $iAlternate parameter uses a TagSort algorithm - this is considerably faster when dealing with multiple columns. However, this algoritm uses more memory and may not be suitable for large arrays on less powerful machines.

Note that there is no guarantee that a specific algorithm will be faster in a given case.

And my suggested recode of the _ArraySort functions:

#include <Array.au3>

; #FUNCTION# ====================================================================================================================
; Author ........: Jos
; Modified.......: LazyCoder - added $iSubItem option; Tylo - implemented stable QuickSort algo; Jos - changed logic to correctly Sort arrays with mixed Values and Strings
; Melba23 - implemented stable pivot algo; czardas - speed optimization for 2D arrays
; ===============================================================================================================================
Func _ArraySort_NEW(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iAlternate = 0)

    If $iDescending = Default Then $iDescending = 0
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iSubItem = Default Then $iSubItem = 0
    If $iAlternate = Default Then $iAlternate = 0
    If Not IsArray($aArray) Then Return SetError(1, 0, 0)

    Local $iUBound = UBound($aArray) - 1
    If $iUBound = -1 Then Return SetError(5, 0, 0)

    ; Bounds checking
    If $iEnd = Default Then $iEnd = 0
    If $iEnd < 1 Or $iEnd > $iUBound Or $iEnd = Default Then $iEnd = $iUBound
    If $iStart < 0 Or $iStart = Default Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(2, 0, 0)
    If $iDescending = Default Then $iDescending = 0
    If $iAlternate = Default Then $iAlternate = 0
    If $iSubItem = Default Then $iSubItem = 0
    ; Sort
    Switch UBound($aArray, $UBOUND_DIMENSIONS)
        Case 1
            If $iAlternate Then ; Use PivotSort algorithm
                __ArrayDualPivotSort1D_New($aArray, $iStart, $iEnd)
            Else
                __ArrayQuickSort1D_New($aArray, $iStart, $iEnd)
            EndIf
            If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd)
        Case 2
            Local $iSubMax = UBound($aArray, $UBOUND_COLUMNS) - 1
            If $iSubItem > $iSubMax Then Return SetError(3, 0, 0)
            If $iDescending Then
                $iDescending = -1
            Else
                $iDescending = 1
            EndIf
            If $iAlternate Then ; Use TagSort algorithm
                Local $aTrac[$iUBound +1]
                For $i = $iStart To $iEnd
                    $aTrac[$i] = $i
                Next
                __ArrayTagSort2D($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
                __ArrayTagSort2D_SwapSeq($aArray, $aTrac, $iStart, $iEnd)
            Else
                __ArrayQuickSort2D($aArray, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
            EndIf
        Case Else
            Return SetError(4, 0, 0)
    EndSwitch
    Return 1
EndFunc   ;==>_ArraySort

; 1D Sort helper functions

Func __ArrayQuickSort1D_New(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd)
    If $iEnd <= $iStart Then Return

    Local $vTmp

    ; InsertionSort used for small arrays - value chosen empirically
    If ($iEnd - $iStart) < 15 Then
        __ArrayInsertSort1D($aArray, $iStart, $iEnd)
        Return
    EndIf

    ; QuickSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[Int(($iStart + $iEnd) / 2)], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            While ($aArray[$L] < $vPivot And IsNumber($aArray[$L])) Or (Not IsNumber($aArray[$L]) And StringCompare($aArray[$L], $vPivot) < 0)
                $L += 1
            WEnd
            While ($aArray[$R] > $vPivot And IsNumber($aArray[$R])) Or (Not IsNumber($aArray[$R]) And StringCompare($aArray[$R], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While (StringCompare($aArray[$L], $vPivot) < 0)
                $L += 1
            WEnd
            While (StringCompare($aArray[$R], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf

        ; Swap
        If $L <= $R Then
            $vTmp = $aArray[$L]
            $aArray[$L] = $aArray[$R]
            $aArray[$R] = $vTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R

    __ArrayQuickSort1D($aArray, $iStart, $R)
    __ArrayQuickSort1D($aArray, $L, $iEnd)
EndFunc   ;==>__ArrayQuickSort1D

Func __ArrayDualPivotSort1D_New(ByRef $aArray, $iPivot_Left, $iPivot_Right)
    If $iPivot_Left > $iPivot_Right Then Return
    Local $iLength = $iPivot_Right - $iPivot_Left + 1
    ;Local $i, $j, $k, $iAi, $iAk, $iA1, $iA2, $iLast
    Local $k
    ; InsertionSort used for small arrays - value chosen empirically
    If $iLength < 45 Then
        __ArrayInsertSort1D($aArray, $iPivot_Left, $iPivot_Right)
        Return
    EndIf
    ; PivotSort
    Local $iSeventh = BitShift($iLength, 3) + BitShift($iLength, 6) + 1
    Local $iE1, $iE2, $iE3, $iE4, $iE5, $t
    $iE3 = Ceiling(($iPivot_Left + $iPivot_Right) / 2)
    $iE2 = $iE3 - $iSeventh
    $iE1 = $iE2 - $iSeventh
    $iE4 = $iE3 + $iSeventh
    $iE5 = $iE4 + $iSeventh
    If $aArray[$iE2] < $aArray[$iE1] Then
        $t = $aArray[$iE2]
        $aArray[$iE2] = $aArray[$iE1]
        $aArray[$iE1] = $t
    EndIf
    If $aArray[$iE3] < $aArray[$iE2] Then
        $t = $aArray[$iE3]
        $aArray[$iE3] = $aArray[$iE2]
        $aArray[$iE2] = $t
        If $t < $aArray[$iE1] Then
            $aArray[$iE2] = $aArray[$iE1]
            $aArray[$iE1] = $t
        EndIf
    EndIf
    If $aArray[$iE4] < $aArray[$iE3] Then
        $t = $aArray[$iE4]
        $aArray[$iE4] = $aArray[$iE3]
        $aArray[$iE3] = $t
        If $t < $aArray[$iE2] Then
            $aArray[$iE3] = $aArray[$iE2]
            $aArray[$iE2] = $t
            If $t < $aArray[$iE1] Then
                $aArray[$iE2] = $aArray[$iE1]
                $aArray[$iE1] = $t
            EndIf
        EndIf
    EndIf
    If $aArray[$iE5] < $aArray[$iE4] Then
        $t = $aArray[$iE5]
        $aArray[$iE5] = $aArray[$iE4]
        $aArray[$iE4] = $t
        If $t < $aArray[$iE3] Then
            $aArray[$iE4] = $aArray[$iE3]
            $aArray[$iE3] = $t
            If $t < $aArray[$iE2] Then
                $aArray[$iE3] = $aArray[$iE2]
                $aArray[$iE2] = $t
                If $t < $aArray[$iE1] Then
                    $aArray[$iE2] = $aArray[$iE1]
                    $aArray[$iE1] = $t
                EndIf
            EndIf
        EndIf
    EndIf
    Local $iLess = $iPivot_Left
    Local $iGreater = $iPivot_Right
    If (($aArray[$iE1] <> $aArray[$iE2]) And ($aArray[$iE2] <> $aArray[$iE3]) And ($aArray[$iE3] <> $aArray[$iE4]) And ($aArray[$iE4] <> $aArray[$iE5])) Then
        Local $iPivot_1 = $aArray[$iE2]
        Local $iPivot_2 = $aArray[$iE4]
        $aArray[$iE2] = $aArray[$iPivot_Left]
        $aArray[$iE4] = $aArray[$iPivot_Right]
        Do
            $iLess += 1
        Until $aArray[$iLess] >= $iPivot_1
        Do
            $iGreater -= 1
        Until $aArray[$iGreater] <= $iPivot_2
        $k = $iLess
        Local $iAk
        While $k <= $iGreater
            $iAk = $aArray[$k]
            If $iAk < $iPivot_1 Then
                $aArray[$k] = $aArray[$iLess]
                $aArray[$iLess] = $iAk
                $iLess += 1
            ElseIf $iAk > $iPivot_2 Then
                While $aArray[$iGreater] > $iPivot_2
                    $iGreater -= 1
                    If $iGreater + 1 = $k Then ExitLoop 2
                WEnd
                If $aArray[$iGreater] < $iPivot_1 Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $aArray[$iGreater]
                    $iLess += 1
                Else
                    $aArray[$k] = $aArray[$iGreater]
                EndIf
                $aArray[$iGreater] = $iAk
                $iGreater -= 1
            EndIf
            $k += 1
        WEnd
        $aArray[$iPivot_Left] = $aArray[$iLess - 1]
        $aArray[$iLess - 1] = $iPivot_1
        $aArray[$iPivot_Right] = $aArray[$iGreater + 1]
        $aArray[$iGreater + 1] = $iPivot_2
        __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 2)
        __ArrayDualPivotSort1D_New($aArray, $iGreater + 2, $iPivot_Right)
        If ($iLess < $iE1) And ($iE5 < $iGreater) Then
            While $aArray[$iLess] = $iPivot_1
                $iLess += 1
            WEnd
            While $aArray[$iGreater] = $iPivot_2
                $iGreater -= 1
            WEnd
            $k = $iLess
            While $k <= $iGreater
                $iAk = $aArray[$k]
                If $iAk = $iPivot_1 Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $iAk
                    $iLess += 1
                ElseIf $iAk = $iPivot_2 Then
                    While $aArray[$iGreater] = $iPivot_2
                        $iGreater -= 1
                        If $iGreater + 1 = $k Then ExitLoop 2
                    WEnd
                    If $aArray[$iGreater] = $iPivot_1 Then
                        $aArray[$k] = $aArray[$iLess]
                        $aArray[$iLess] = $iPivot_1
                        $iLess += 1
                    Else
                        $aArray[$k] = $aArray[$iGreater]
                    EndIf
                    $aArray[$iGreater] = $iAk
                    $iGreater -= 1
                EndIf
                $k += 1
            WEnd
        EndIf
        __ArrayDualPivotSort1D_New($aArray, $iLess, $iGreater)
    Else
        Local $iPivot = $aArray[$iE3]
        $k = $iLess
        While $k <= $iGreater
            If $aArray[$k] = $iPivot Then
                $k += 1
                ContinueLoop
            EndIf
            $iAk = $aArray[$k]
            If $iAk < $iPivot Then
                $aArray[$k] = $aArray[$iLess]
                $aArray[$iLess] = $iAk
                $iLess += 1
            Else
                While $aArray[$iGreater] > $iPivot
                    $iGreater -= 1
                WEnd
                If $aArray[$iGreater] < $iPivot Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $aArray[$iGreater]
                    $iLess += 1
                Else
                    $aArray[$k] = $iPivot
                EndIf
                $aArray[$iGreater] = $iAk
                $iGreater -= 1
            EndIf
            $k += 1
        WEnd
        __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 1)
        __ArrayDualPivotSort1D_New($aArray, $iGreater + 1, $iPivot_Right)
    EndIf
EndFunc   ;==>__ArrayDualPivotSort1D

Func __ArrayInsertSort1D(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd)

    Local $vCur, $vTmp
        For $i = $iStart + 1 To $iEnd
            $vTmp = $aArray[$i]
            If IsNumber($vTmp) Then
                For $j = $i - 1 To $iStart Step -1
                    $vCur = $aArray[$j]
                    If ($vTmp >= $vCur And IsNumber($vCur)) Or (Not IsNumber($vCur) And StringCompare($vTmp, $vCur) >= 0) Then ExitLoop
                    $aArray[$j + 1] = $vCur
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($vTmp, $aArray[$j]) >= 0) Then ExitLoop
                    $aArray[$j + 1] = $aArray[$j]
                Next
            EndIf
            $aArray[$j + 1] = $vTmp
        Next

EndFunc

; 2D Sort helper functions

; Existing __ArrayQuickSort2D

Func __ArrayTagSort2D(Const ByRef $aArray, ByRef $aTrac, Const ByRef $iStep, Const ByRef $iStart, Const ByRef $iEnd, Const ByRef $iSubItem, Const ByRef $iSubMax)
    If $iEnd <= $iStart Then Return
    Local $vTmp
    ; InsertionSort (faster for smaller segments)
    If ($iEnd - $iStart) < 1 Then   ; Force tagsort
        For $i = $iStart + 1 To $iEnd
            $vTmp = $aTrac[$i]

            If IsNumber($aArray[$vTmp][$iSubItem]) Then
                For $j = $i - 1 To $iStart Step -1
                    If ((($aArray[$vTmp][$iSubItem] >= $aArray[$aTrac[$j]][$iSubItem] And $iStep = 1) Or $aArray[$vTmp][$iSubItem] <= $aArray[$aTrac[$j]][$iSubItem]) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($aArray[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            EndIf

            $aTrac[$j + 1] = $vTmp
        Next
        Return
    EndIf
    ; TagSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            While ($iStep * ($aArray[$aTrac[$L]][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$aTrac[$L]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$L]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * ($aArray[$aTrac[$R]][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$aTrac[$R]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$R]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While ($iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf
        If $L <= $R Then ; Swap
            $vTmp = $aTrac[$L]
            $aTrac[$L] = $aTrac[$R]
            $aTrac[$R] = $vTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R
    __ArrayTagSort2D($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax)
    __ArrayTagSort2D($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax)
EndFunc   ;==>__ArrayQuickSort2D_NEW2

Func __ArrayTagSort2D_SwapSeq(ByRef $aArray, ByRef $aTrac, Const ByRef $iStart, Const ByRef $iEnd)
    Local $iCols = UBound($aArray, 2), $aFirst[$iCols], $i, $iNext

    For $iInit = $iStart To $iEnd ; initialize each potential overwrite sequence [separate closed system]
        If $aTrac[$iInit] <> $iInit Then ; rows will now be overwritten in accordance with tracking information
            $i = $iInit ; set the current row as the start of the sequence
            For $j = 0 To $iCols -1
                $aFirst[$j] = $aArray[$i][$j] ; copy the first row [although we don't know where to put it yet]
            Next
            Do
                For $j = 0 To $iCols -1
                    $aArray[$i][$j] = $aArray[$aTrac[$i]][$j] ; overwrite each row [following the trail]
                Next
                $iNext = $aTrac[$i] ; get the index of the next row in the sequence
                $aTrac[$i] = $i ; set to ignore rows already processed [may be needed once, or not at all]
                $i = $iNext ; follow the trail as far as it goes [indices could be higher or lower]
            Until $aTrac[$i] = $iInit ; all tracking sequences end at this juncture
            For $j = 0 To $iCols -1
                $aArray[$i][$j] = $aFirst[$j] ; now we know where to put the initial row we copied earlier
            Next
            $aTrac[$i] = $i ; set to ignore rows already processed [as above]
        EndIf
    Next
EndFunc ;==> __ArrayTagSort2D_SwapSeq

Other than the insertion of your TagSort code, the main change is that I have extracted the insertionSort sections in both the __ArrayQuickSort1D_New & __ArrayDualPivotSort1D_New functions into a separate function - you may remember that we found that the existing InsertionSort code in the PivotSort algorithm gave erroneous results for empty elements. As the solution was to use the same code for both, it seemed logical to have it just the once.

M23

czardas · May 10, 2016

Ha that's funny: our descriptions are almost identical. It all looks fine to me, although I haven't tested anything yet. I do remember the thread you mentioned.

Edit: Some checks appear duplicated - I removed them earlier.

; Bounds checking
    If $iEnd = Default Then $iEnd = 0
    If $iEnd < 1 Or $iEnd > $iUBound Or $iEnd = Default Then $iEnd = $iUBound
    If $iStart < 0 Or $iStart = Default Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(2, 0, 0)
    ;If $iDescending = Default Then $iDescending = 0
    ;If $iAlternate = Default Then $iAlternate = 0
    ;If $iSubItem = Default Then $iSubItem = 0

@Melba23 See my edit here.

Edited May 10, 2016 by czardas

czardas · May 10, 2016

Maybe you could also change this

; czardas - speed optimization for 2D arrays

to this

; czardas - implemented tag sort

And this line

If $iAlternate Then ; Use TagSort algorithm

to this

If $iAlternate And $iSubMax Then ; Use TagSort algorithm

because tag sort will always be slower with only 1 column ($iSubMax = 0).

Edited May 10, 2016 by czardas

czardas · February 5, 2018

The inclusion of Tag Sort (for 2D arrays) could do with more testing, if any of you can give this a try. It may be added to the next beta, so please could some of you try this. I have been using it for quite a while already without problems. @Melba23 I reverted the two changes we discussed earlier. I haven't looked at any of the code for __ArrayDualPivotSort1D_New(). I'm assuming it is the same as for the current release, unless you changed something else.

$iAlternate [optional]  1D array sorted with PivotSort algorithm
            2D array sorted with TagSort algorithm
            Default: both sorted with QuickSort algorithm

Return Value
Success: 1. 
Failure: 0 and sets the @error flag to non-zero. 
@error:  1 - $aArray is not an array
2 - $iStart is greater than $iEnd
3 - $iSubItem is greater than subitem count
4 - $aArray is not a 1D or 2D array
5 - $aArray is empty
6 - Deprecated

Remarks
By default the UDF uses a QuickSort algorithm to sort both 1D and 2D arrays.

For 1D arrays setting the $iAlternate parameter uses a DualPivotSort algorithm - this can be significantly faster for large arrays (> 50 elements). In each algorithm, relatively short arrays will be sorted using an insertion sort (< 15 elements with QuickSort and TagSort; < 45 elements with Dual PivotSort).

For 2D arrays setting the $iAlternate parameter uses a TagSort algorithm - this is considerably faster when dealing with multiple columns. However, this algoritm uses more memory and may not be suitable for large arrays on less powerful machines.

Note that there is no guarantee that a specific algorithm will be faster in a given case.

CODE: - CONTAINS A BUG (fixed in post #52 below)

#include <Array.au3>

; #FUNCTION# ====================================================================================================================
; Author ........: Jos
; Modified.......: LazyCoder - added $iSubItem option; Tylo - implemented stable QuickSort algo; Jos - changed logic to correctly Sort arrays with mixed Values and Strings
; Melba23 - implemented stable pivot algo; czardas - implemented TagSort
; ===============================================================================================================================
Func _ArraySort_NEW(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iAlternate = 0)

    If $iDescending = Default Then $iDescending = 0
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iSubItem = Default Then $iSubItem = 0
    If $iAlternate = Default Then $iAlternate = 0
    If Not IsArray($aArray) Then Return SetError(1, 0, 0)

    Local $iUBound = UBound($aArray) - 1
    If $iUBound = -1 Then Return SetError(5, 0, 0)

    ; Bounds checking
    If $iEnd < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(2, 0, 0)

    ; Sort
    Switch UBound($aArray, $UBOUND_DIMENSIONS)
        Case 1
            If $iAlternate Then ; Use PivotSort algorithm
                __ArrayDualPivotSort1D_New($aArray, $iStart, $iEnd)
            Else
                __ArrayQuickSort1D_New($aArray, $iStart, $iEnd)
            EndIf
            If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd)
        Case 2
            Local $iSubMax = UBound($aArray, $UBOUND_COLUMNS) - 1
            If $iSubItem > $iSubMax Then Return SetError(3, 0, 0)
            If $iDescending Then
                $iDescending = -1
            Else
                $iDescending = 1
            EndIf
            If $iAlternate And $iSubMax Then ; Use TagSort algorithm
                Local $aTrac[$iUBound +1]
                For $i = $iStart To $iEnd
                    $aTrac[$i] = $i
                Next
                __ArrayTagSort2D($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
                __ArrayTagSort2D_SwapSeq($aArray, $aTrac, $iStart, $iEnd)
            Else
                __ArrayQuickSort2D($aArray, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
            EndIf
        Case Else
            Return SetError(4, 0, 0)
    EndSwitch
    Return 1
EndFunc   ;==>_ArraySort

; 1D Sort helper functions

Func __ArrayQuickSort1D_New(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd)
    If $iEnd <= $iStart Then Return

    Local $vTmp

    ; InsertionSort used for small arrays - value chosen empirically
    If ($iEnd - $iStart) < 15 Then
        __ArrayInsertSort1D($aArray, $iStart, $iEnd)
        Return
    EndIf

    ; QuickSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[Int(($iStart + $iEnd) / 2)], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            While ($aArray[$L] < $vPivot And IsNumber($aArray[$L])) Or (Not IsNumber($aArray[$L]) And StringCompare($aArray[$L], $vPivot) < 0)
                $L += 1
            WEnd
            While ($aArray[$R] > $vPivot And IsNumber($aArray[$R])) Or (Not IsNumber($aArray[$R]) And StringCompare($aArray[$R], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While (StringCompare($aArray[$L], $vPivot) < 0)
                $L += 1
            WEnd
            While (StringCompare($aArray[$R], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf

        ; Swap
        If $L <= $R Then
            $vTmp = $aArray[$L]
            $aArray[$L] = $aArray[$R]
            $aArray[$R] = $vTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R

    __ArrayQuickSort1D($aArray, $iStart, $R)
    __ArrayQuickSort1D($aArray, $L, $iEnd)
EndFunc   ;==>__ArrayQuickSort1D

Func __ArrayDualPivotSort1D_New(ByRef $aArray, $iPivot_Left, $iPivot_Right)
    If $iPivot_Left > $iPivot_Right Then Return
    Local $iLength = $iPivot_Right - $iPivot_Left + 1
    ;Local $i, $j, $k, $iAi, $iAk, $iA1, $iA2, $iLast
    Local $k
    ; InsertionSort used for small arrays - value chosen empirically
    If $iLength < 45 Then
        __ArrayInsertSort1D($aArray, $iPivot_Left, $iPivot_Right)
        Return
    EndIf
    ; PivotSort
    Local $iSeventh = BitShift($iLength, 3) + BitShift($iLength, 6) + 1
    Local $iE1, $iE2, $iE3, $iE4, $iE5, $t
    $iE3 = Ceiling(($iPivot_Left + $iPivot_Right) / 2)
    $iE2 = $iE3 - $iSeventh
    $iE1 = $iE2 - $iSeventh
    $iE4 = $iE3 + $iSeventh
    $iE5 = $iE4 + $iSeventh
    If $aArray[$iE2] < $aArray[$iE1] Then
        $t = $aArray[$iE2]
        $aArray[$iE2] = $aArray[$iE1]
        $aArray[$iE1] = $t
    EndIf
    If $aArray[$iE3] < $aArray[$iE2] Then
        $t = $aArray[$iE3]
        $aArray[$iE3] = $aArray[$iE2]
        $aArray[$iE2] = $t
        If $t < $aArray[$iE1] Then
            $aArray[$iE2] = $aArray[$iE1]
            $aArray[$iE1] = $t
        EndIf
    EndIf
    If $aArray[$iE4] < $aArray[$iE3] Then
        $t = $aArray[$iE4]
        $aArray[$iE4] = $aArray[$iE3]
        $aArray[$iE3] = $t
        If $t < $aArray[$iE2] Then
            $aArray[$iE3] = $aArray[$iE2]
            $aArray[$iE2] = $t
            If $t < $aArray[$iE1] Then
                $aArray[$iE2] = $aArray[$iE1]
                $aArray[$iE1] = $t
            EndIf
        EndIf
    EndIf
    If $aArray[$iE5] < $aArray[$iE4] Then
        $t = $aArray[$iE5]
        $aArray[$iE5] = $aArray[$iE4]
        $aArray[$iE4] = $t
        If $t < $aArray[$iE3] Then
            $aArray[$iE4] = $aArray[$iE3]
            $aArray[$iE3] = $t
            If $t < $aArray[$iE2] Then
                $aArray[$iE3] = $aArray[$iE2]
                $aArray[$iE2] = $t
                If $t < $aArray[$iE1] Then
                    $aArray[$iE2] = $aArray[$iE1]
                    $aArray[$iE1] = $t
                EndIf
            EndIf
        EndIf
    EndIf
    Local $iLess = $iPivot_Left
    Local $iGreater = $iPivot_Right
    If (($aArray[$iE1] <> $aArray[$iE2]) And ($aArray[$iE2] <> $aArray[$iE3]) And ($aArray[$iE3] <> $aArray[$iE4]) And ($aArray[$iE4] <> $aArray[$iE5])) Then
        Local $iPivot_1 = $aArray[$iE2]
        Local $iPivot_2 = $aArray[$iE4]
        $aArray[$iE2] = $aArray[$iPivot_Left]
        $aArray[$iE4] = $aArray[$iPivot_Right]
        Do
            $iLess += 1
        Until $aArray[$iLess] >= $iPivot_1
        Do
            $iGreater -= 1
        Until $aArray[$iGreater] <= $iPivot_2
        $k = $iLess
        Local $iAk
        While $k <= $iGreater
            $iAk = $aArray[$k]
            If $iAk < $iPivot_1 Then
                $aArray[$k] = $aArray[$iLess]
                $aArray[$iLess] = $iAk
                $iLess += 1
            ElseIf $iAk > $iPivot_2 Then
                While $aArray[$iGreater] > $iPivot_2
                    $iGreater -= 1
                    If $iGreater + 1 = $k Then ExitLoop 2
                WEnd
                If $aArray[$iGreater] < $iPivot_1 Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $aArray[$iGreater]
                    $iLess += 1
                Else
                    $aArray[$k] = $aArray[$iGreater]
                EndIf
                $aArray[$iGreater] = $iAk
                $iGreater -= 1
            EndIf
            $k += 1
        WEnd
        $aArray[$iPivot_Left] = $aArray[$iLess - 1]
        $aArray[$iLess - 1] = $iPivot_1
        $aArray[$iPivot_Right] = $aArray[$iGreater + 1]
        $aArray[$iGreater + 1] = $iPivot_2
        __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 2)
        __ArrayDualPivotSort1D_New($aArray, $iGreater + 2, $iPivot_Right)
        If ($iLess < $iE1) And ($iE5 < $iGreater) Then
            While $aArray[$iLess] = $iPivot_1
                $iLess += 1
            WEnd
            While $aArray[$iGreater] = $iPivot_2
                $iGreater -= 1
            WEnd
            $k = $iLess
            While $k <= $iGreater
                $iAk = $aArray[$k]
                If $iAk = $iPivot_1 Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $iAk
                    $iLess += 1
                ElseIf $iAk = $iPivot_2 Then
                    While $aArray[$iGreater] = $iPivot_2
                        $iGreater -= 1
                        If $iGreater + 1 = $k Then ExitLoop 2
                    WEnd
                    If $aArray[$iGreater] = $iPivot_1 Then
                        $aArray[$k] = $aArray[$iLess]
                        $aArray[$iLess] = $iPivot_1
                        $iLess += 1
                    Else
                        $aArray[$k] = $aArray[$iGreater]
                    EndIf
                    $aArray[$iGreater] = $iAk
                    $iGreater -= 1
                EndIf
                $k += 1
            WEnd
        EndIf
        __ArrayDualPivotSort1D_New($aArray, $iLess, $iGreater)
    Else
        Local $iPivot = $aArray[$iE3]
        $k = $iLess
        While $k <= $iGreater
            If $aArray[$k] = $iPivot Then
                $k += 1
                ContinueLoop
            EndIf
            $iAk = $aArray[$k]
            If $iAk < $iPivot Then
                $aArray[$k] = $aArray[$iLess]
                $aArray[$iLess] = $iAk
                $iLess += 1
            Else
                While $aArray[$iGreater] > $iPivot
                    $iGreater -= 1
                WEnd
                If $aArray[$iGreater] < $iPivot Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $aArray[$iGreater]
                    $iLess += 1
                Else
                    $aArray[$k] = $iPivot
                EndIf
                $aArray[$iGreater] = $iAk
                $iGreater -= 1
            EndIf
            $k += 1
        WEnd
        __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 1)
        __ArrayDualPivotSort1D_New($aArray, $iGreater + 1, $iPivot_Right)
    EndIf
EndFunc   ;==>__ArrayDualPivotSort1D

Func __ArrayInsertSort1D(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd)

    Local $vCur, $vTmp
        For $i = $iStart + 1 To $iEnd
            $vTmp = $aArray[$i]
            If IsNumber($vTmp) Then
                For $j = $i - 1 To $iStart Step -1
                    $vCur = $aArray[$j]
                    If ($vTmp >= $vCur And IsNumber($vCur)) Or (Not IsNumber($vCur) And StringCompare($vTmp, $vCur) >= 0) Then ExitLoop
                    $aArray[$j + 1] = $vCur
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($vTmp, $aArray[$j]) >= 0) Then ExitLoop
                    $aArray[$j + 1] = $aArray[$j]
                Next
            EndIf
            $aArray[$j + 1] = $vTmp
        Next

EndFunc

; 2D Sort helper functions

; Existing __ArrayQuickSort2D

Func __ArrayTagSort2D(Const ByRef $aArray, ByRef $aTrac, Const ByRef $iStep, Const ByRef $iStart, Const ByRef $iEnd, Const ByRef $iSubItem, Const ByRef $iSubMax)
    If $iEnd <= $iStart Then Return
    Local $vTmp
    ; InsertionSort (faster for smaller segments)
    If ($iEnd - $iStart) < 15 Then   ; Force tagsort
        For $i = $iStart + 1 To $iEnd
            $vTmp = $aTrac[$i]

            If IsNumber($aArray[$vTmp][$iSubItem]) Then
                For $j = $i - 1 To $iStart Step -1
                    If ((($aArray[$vTmp][$iSubItem] >= $aArray[$aTrac[$j]][$iSubItem] And $iStep = 1) Or $aArray[$vTmp][$iSubItem] <= $aArray[$aTrac[$j]][$iSubItem]) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($aArray[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            EndIf

            $aTrac[$j + 1] = $vTmp
        Next
        Return
    EndIf
    ; TagSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            While ($iStep * ($aArray[$aTrac[$L]][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$aTrac[$L]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$L]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * ($aArray[$aTrac[$R]][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$aTrac[$R]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$R]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While ($iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf
        If $L <= $R Then ; Swap
            $vTmp = $aTrac[$L]
            $aTrac[$L] = $aTrac[$R]
            $aTrac[$R] = $vTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R
    __ArrayTagSort2D($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax)
    __ArrayTagSort2D($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax)
EndFunc   ;==>__ArrayQuickSort2D_NEW2

Func __ArrayTagSort2D_SwapSeq(ByRef $aArray, ByRef $aTrac, Const ByRef $iStart, Const ByRef $iEnd)
    Local $iCols = UBound($aArray, 2), $aFirst[$iCols], $i, $iNext

    For $iInit = $iStart To $iEnd ; initialize each potential overwrite sequence [separate closed system]
        If $aTrac[$iInit] <> $iInit Then ; rows will now be overwritten in accordance with tracking information
            $i = $iInit ; set the current row as the start of the sequence
            For $j = 0 To $iCols -1
                $aFirst[$j] = $aArray[$i][$j] ; copy the first row [although we don't know where to put it yet]
            Next
            Do
                For $j = 0 To $iCols -1
                    $aArray[$i][$j] = $aArray[$aTrac[$i]][$j] ; overwrite each row [following the trail]
                Next
                $iNext = $aTrac[$i] ; get the index of the next row in the sequence
                $aTrac[$i] = $i ; set to ignore rows already processed [may be needed once, or not at all]
                $i = $iNext ; follow the trail as far as it goes [indices could be higher or lower]
            Until $aTrac[$i] = $iInit ; all tracking sequences end at this juncture
            For $j = 0 To $iCols -1
                $aArray[$i][$j] = $aFirst[$j] ; now we know where to put the initial row we copied earlier
            Next
            $aTrac[$i] = $i ; set to ignore rows already processed [as above]
        EndIf
    Next
EndFunc ;==> __ArrayTagSort2D_SwapSeq

Please report tests carried out. You don't need to give full details unless you discover something wrong with it. Thanks!

~~I can't find anything wrong with it.~~

Edited February 6, 2018 by czardas

JLogan3o13 · February 5, 2018

I did some testing this morning on a mid-size array (37 col by c. 200 rows), below are the averages over 10 runs of each:

Current ArraySort - 68.94
New ArraySort without the $iAlternate parameter set - 103.30
New ArraySort with the $iAlternate parameter set - 22.00

czardas · February 5, 2018

Hmm. Not what I expected. There should essentially be no time penalty for using the default sorting method. I'll need to take a closer look. I missed a couple of duplicated error checks, but that shouldn't be slowing it down by much. Code updated in #45. Something about this doesn't add up.

Edited February 5, 2018 by czardas

czardas · February 5, 2018

I'm not able to confirm your results. Here's my test:

Local $aTemp[200][37]
For $a = 0 To UBound($aTemp) -1
    For $b = 0 To UBound($aTemp, 2) -1
        $aTemp[$a][$b] = Chr(Random(97, 122, 1)) & Chr(Random(97, 122, 1)) & Chr(Random(97, 122, 1)) & Chr(Random(97, 122, 1))
    Next
Next

Local $iTimer, $aArray, $iDiff1 = 0, $iDiff2 = 0

For $i = 1 to 10
    $aArray = $aTemp
    $iTimer = TimerInit()
    _ArraySort($aArray)
    $iDiff1 += TimerDiff($iTimer)
Next

ConsoleWrite($iDiff1/10 & @LF)

For $i = 1 to 10
    $aArray = $aTemp
    $iTimer = TimerInit()
    _ArraySort_NEW($aArray)
    $iDiff2 += TimerDiff($iTimer)
Next

ConsoleWrite($iDiff2/10 & @LF)

And the results are very close for the default sorting method (no time penalty):

current version 72.973931289915
new version     72.6573964490579

Perhaps you overlooked something in your test, because the results I'm getting are quite consistent.

With TagSort I get: 27.0241028812861 ms

Edited February 6, 2018 by czardas

JLogan3o13 · February 6, 2018

I'll mess with it some more, and will try with an Array I can post

czardas · February 6, 2018

Thanks for taking the time to look at it. Everyone seems quite busy ATM - including me. :frantics:

There was a suggestion in GH&S to add case sensitivity to _ArraySort() because Maps use case sensitive keys and you might want to sort them this way. This can be easily implemented with QuickSort, but not with Dual PivotSort. I think this is also worth looking into. I did a quick trial run earlier on. In this case; with an additional case sensitivity parameter set, I think it would be best to override Dual PivotSort rather than try to modify it. Otherwise default Dual PivotSort speed would be heavily compromised. Best not to combine these two things.

Edited February 6, 2018 by czardas

czardas · February 6, 2018

A new bug has been introduced: numbers are no longer being sorted correctly. This bug appears to have been introduced with changes made by Melba23 to the InsertionSort section of __ArrayTagSort2D() in post #42. The problem does not occur with the earlier version: _ArraySort_Beta() in post #32. The problem has been fixed below.

Edited February 6, 2018 by czardas

czardas · February 6, 2018

I reverted to the earlier version and it seems to be working again. The bug was not apparent because that section of code was being skipped after changes had been made. When I reintroduced insertion sort by changing the range limit back to what it had been previously, the bug showed itself. The logic had been modified and I was unaware of this. I hope there are no more changes I'm unaware of. I hadn't noticed it because I use my own version.

Description:
Sort a 1D or 2D array on a specific index using the dualpivotsort/quicksort/insertionsort/tagsort algorithms

Syntax:
_ArraySort ( ByRef $aArray [, $iDescending = 0 [, $iStart = 0 [, $iEnd = 0 [, $iSubItem = 0 [, $iAlternate = 0]]]]] )

$iAlternate [optional]  1D array sorted with PivotSort algorithm
            2D array sorted with TagSort algorithm
            Default: both sorted with QuickSort algorithm

Return Value
Success: 1. 
Failure: 0 and sets the @error flag to non-zero. 
@error:  1 - $aArray is not an array
2 - $iStart is greater than $iEnd
3 - $iSubItem is greater than subitem count
4 - $aArray is not a 1D or 2D array
5 - $aArray is empty
6 - Deprecated

Remarks
By default the UDF uses a QuickSort algorithm to sort both 1D and 2D arrays.

For 1D arrays setting the $iAlternate parameter uses a DualPivotSort algorithm - this can be significantly faster for large arrays (> 50 elements). In each algorithm, relatively short arrays will be sorted using an insertion sort (< 15 elements with QuickSort and TagSort; < 45 elements with Dual PivotSort).

For 2D arrays setting the $iAlternate parameter uses a TagSort algorithm - this is considerably faster when dealing with multiple columns. However, this algoritm uses more memory and may not be suitable for large arrays on less powerful machines.

Note that there is no guarantee that a specific algorithm will be faster in a given case.

CODE:

#include <Array.au3>

; #FUNCTION# ====================================================================================================================
; Author ........: Jos
; Modified.......: LazyCoder - added $iSubItem option; Tylo - implemented stable QuickSort algo; Jos - changed logic to correctly Sort arrays with mixed Values and Strings
; Melba23 - implemented stable pivot algo; czardas - implemented TagSort
; ===============================================================================================================================
Func _ArraySort_NEW(ByRef $aArray, $iDescending = 0, $iStart = 0, $iEnd = 0, $iSubItem = 0, $iAlternate = 0)

    If $iDescending = Default Then $iDescending = 0
    If $iStart = Default Then $iStart = 0
    If $iEnd = Default Then $iEnd = 0
    If $iSubItem = Default Then $iSubItem = 0
    If $iAlternate = Default Then $iAlternate = 0
    If Not IsArray($aArray) Then Return SetError(1, 0, 0)

    Local $iUBound = UBound($aArray) - 1
    If $iUBound = -1 Then Return SetError(5, 0, 0)

    ; Bounds checking
    If $iEnd < 1 Or $iEnd > $iUBound Then $iEnd = $iUBound
    If $iStart < 0 Then $iStart = 0
    If $iStart > $iEnd Then Return SetError(2, 0, 0)

    ; Sort
    Switch UBound($aArray, $UBOUND_DIMENSIONS)
        Case 1
            If $iAlternate Then ; Use PivotSort algorithm
                __ArrayDualPivotSort1D_New($aArray, $iStart, $iEnd)
            Else
                __ArrayQuickSort1D_New($aArray, $iStart, $iEnd)
            EndIf
            If $iDescending Then _ArrayReverse($aArray, $iStart, $iEnd)
        Case 2
            Local $iSubMax = UBound($aArray, $UBOUND_COLUMNS) - 1
            If $iSubItem > $iSubMax Then Return SetError(3, 0, 0)
            If $iDescending Then
                $iDescending = -1
            Else
                $iDescending = 1
            EndIf
            If $iAlternate And $iSubMax Then ; Use TagSort algorithm
                Local $aTrac[$iUBound +1]
                For $i = $iStart To $iEnd
                    $aTrac[$i] = $i
                Next
                __ArrayTagSort2D($aArray, $aTrac, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
                __ArrayTagSort2D_SwapSeq($aArray, $aTrac, $iStart, $iEnd)
            Else
                __ArrayQuickSort2D($aArray, $iDescending, $iStart, $iEnd, $iSubItem, $iSubMax)
            EndIf
        Case Else
            Return SetError(4, 0, 0)
    EndSwitch
    Return 1
EndFunc   ;==>_ArraySort

; 1D Sort helper functions

Func __ArrayQuickSort1D_New(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd)
    If $iEnd <= $iStart Then Return

    Local $vTmp

    ; InsertionSort used for small arrays - value chosen empirically
    If ($iEnd - $iStart) < 15 Then
        __ArrayInsertSort1D($aArray, $iStart, $iEnd)
        Return
    EndIf

    ; QuickSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[Int(($iStart + $iEnd) / 2)], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            While ($aArray[$L] < $vPivot And IsNumber($aArray[$L])) Or (Not IsNumber($aArray[$L]) And StringCompare($aArray[$L], $vPivot) < 0)
                $L += 1
            WEnd
            While ($aArray[$R] > $vPivot And IsNumber($aArray[$R])) Or (Not IsNumber($aArray[$R]) And StringCompare($aArray[$R], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While (StringCompare($aArray[$L], $vPivot) < 0)
                $L += 1
            WEnd
            While (StringCompare($aArray[$R], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf

        ; Swap
        If $L <= $R Then
            $vTmp = $aArray[$L]
            $aArray[$L] = $aArray[$R]
            $aArray[$R] = $vTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R

    __ArrayQuickSort1D($aArray, $iStart, $R)
    __ArrayQuickSort1D($aArray, $L, $iEnd)
EndFunc   ;==>__ArrayQuickSort1D

Func __ArrayDualPivotSort1D_New(ByRef $aArray, $iPivot_Left, $iPivot_Right)
    If $iPivot_Left > $iPivot_Right Then Return
    Local $iLength = $iPivot_Right - $iPivot_Left + 1
    ;Local $i, $j, $k, $iAi, $iAk, $iA1, $iA2, $iLast
    Local $k
    ; InsertionSort used for small arrays - value chosen empirically
    If $iLength < 45 Then
        __ArrayInsertSort1D($aArray, $iPivot_Left, $iPivot_Right)
        Return
    EndIf
    ; PivotSort
    Local $iSeventh = BitShift($iLength, 3) + BitShift($iLength, 6) + 1
    Local $iE1, $iE2, $iE3, $iE4, $iE5, $t
    $iE3 = Ceiling(($iPivot_Left + $iPivot_Right) / 2)
    $iE2 = $iE3 - $iSeventh
    $iE1 = $iE2 - $iSeventh
    $iE4 = $iE3 + $iSeventh
    $iE5 = $iE4 + $iSeventh
    If $aArray[$iE2] < $aArray[$iE1] Then
        $t = $aArray[$iE2]
        $aArray[$iE2] = $aArray[$iE1]
        $aArray[$iE1] = $t
    EndIf
    If $aArray[$iE3] < $aArray[$iE2] Then
        $t = $aArray[$iE3]
        $aArray[$iE3] = $aArray[$iE2]
        $aArray[$iE2] = $t
        If $t < $aArray[$iE1] Then
            $aArray[$iE2] = $aArray[$iE1]
            $aArray[$iE1] = $t
        EndIf
    EndIf
    If $aArray[$iE4] < $aArray[$iE3] Then
        $t = $aArray[$iE4]
        $aArray[$iE4] = $aArray[$iE3]
        $aArray[$iE3] = $t
        If $t < $aArray[$iE2] Then
            $aArray[$iE3] = $aArray[$iE2]
            $aArray[$iE2] = $t
            If $t < $aArray[$iE1] Then
                $aArray[$iE2] = $aArray[$iE1]
                $aArray[$iE1] = $t
            EndIf
        EndIf
    EndIf
    If $aArray[$iE5] < $aArray[$iE4] Then
        $t = $aArray[$iE5]
        $aArray[$iE5] = $aArray[$iE4]
        $aArray[$iE4] = $t
        If $t < $aArray[$iE3] Then
            $aArray[$iE4] = $aArray[$iE3]
            $aArray[$iE3] = $t
            If $t < $aArray[$iE2] Then
                $aArray[$iE3] = $aArray[$iE2]
                $aArray[$iE2] = $t
                If $t < $aArray[$iE1] Then
                    $aArray[$iE2] = $aArray[$iE1]
                    $aArray[$iE1] = $t
                EndIf
            EndIf
        EndIf
    EndIf
    Local $iLess = $iPivot_Left
    Local $iGreater = $iPivot_Right
    If (($aArray[$iE1] <> $aArray[$iE2]) And ($aArray[$iE2] <> $aArray[$iE3]) And ($aArray[$iE3] <> $aArray[$iE4]) And ($aArray[$iE4] <> $aArray[$iE5])) Then
        Local $iPivot_1 = $aArray[$iE2]
        Local $iPivot_2 = $aArray[$iE4]
        $aArray[$iE2] = $aArray[$iPivot_Left]
        $aArray[$iE4] = $aArray[$iPivot_Right]
        Do
            $iLess += 1
        Until $aArray[$iLess] >= $iPivot_1
        Do
            $iGreater -= 1
        Until $aArray[$iGreater] <= $iPivot_2
        $k = $iLess
        Local $iAk
        While $k <= $iGreater
            $iAk = $aArray[$k]
            If $iAk < $iPivot_1 Then
                $aArray[$k] = $aArray[$iLess]
                $aArray[$iLess] = $iAk
                $iLess += 1
            ElseIf $iAk > $iPivot_2 Then
                While $aArray[$iGreater] > $iPivot_2
                    $iGreater -= 1
                    If $iGreater + 1 = $k Then ExitLoop 2
                WEnd
                If $aArray[$iGreater] < $iPivot_1 Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $aArray[$iGreater]
                    $iLess += 1
                Else
                    $aArray[$k] = $aArray[$iGreater]
                EndIf
                $aArray[$iGreater] = $iAk
                $iGreater -= 1
            EndIf
            $k += 1
        WEnd
        $aArray[$iPivot_Left] = $aArray[$iLess - 1]
        $aArray[$iLess - 1] = $iPivot_1
        $aArray[$iPivot_Right] = $aArray[$iGreater + 1]
        $aArray[$iGreater + 1] = $iPivot_2
        __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 2)
        __ArrayDualPivotSort1D_New($aArray, $iGreater + 2, $iPivot_Right)
        If ($iLess < $iE1) And ($iE5 < $iGreater) Then
            While $aArray[$iLess] = $iPivot_1
                $iLess += 1
            WEnd
            While $aArray[$iGreater] = $iPivot_2
                $iGreater -= 1
            WEnd
            $k = $iLess
            While $k <= $iGreater
                $iAk = $aArray[$k]
                If $iAk = $iPivot_1 Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $iAk
                    $iLess += 1
                ElseIf $iAk = $iPivot_2 Then
                    While $aArray[$iGreater] = $iPivot_2
                        $iGreater -= 1
                        If $iGreater + 1 = $k Then ExitLoop 2
                    WEnd
                    If $aArray[$iGreater] = $iPivot_1 Then
                        $aArray[$k] = $aArray[$iLess]
                        $aArray[$iLess] = $iPivot_1
                        $iLess += 1
                    Else
                        $aArray[$k] = $aArray[$iGreater]
                    EndIf
                    $aArray[$iGreater] = $iAk
                    $iGreater -= 1
                EndIf
                $k += 1
            WEnd
        EndIf
        __ArrayDualPivotSort1D_New($aArray, $iLess, $iGreater)
    Else
        Local $iPivot = $aArray[$iE3]
        $k = $iLess
        While $k <= $iGreater
            If $aArray[$k] = $iPivot Then
                $k += 1
                ContinueLoop
            EndIf
            $iAk = $aArray[$k]
            If $iAk < $iPivot Then
                $aArray[$k] = $aArray[$iLess]
                $aArray[$iLess] = $iAk
                $iLess += 1
            Else
                While $aArray[$iGreater] > $iPivot
                    $iGreater -= 1
                WEnd
                If $aArray[$iGreater] < $iPivot Then
                    $aArray[$k] = $aArray[$iLess]
                    $aArray[$iLess] = $aArray[$iGreater]
                    $iLess += 1
                Else
                    $aArray[$k] = $iPivot
                EndIf
                $aArray[$iGreater] = $iAk
                $iGreater -= 1
            EndIf
            $k += 1
        WEnd
        __ArrayDualPivotSort1D_New($aArray, $iPivot_Left, $iLess - 1)
        __ArrayDualPivotSort1D_New($aArray, $iGreater + 1, $iPivot_Right)
    EndIf
EndFunc   ;==>__ArrayDualPivotSort1D

Func __ArrayInsertSort1D(ByRef $aArray, Const ByRef $iStart, Const ByRef $iEnd)

    Local $vCur, $vTmp
        For $i = $iStart + 1 To $iEnd
            $vTmp = $aArray[$i]
            If IsNumber($vTmp) Then
                For $j = $i - 1 To $iStart Step -1
                    $vCur = $aArray[$j]
                    If ($vTmp >= $vCur And IsNumber($vCur)) Or (Not IsNumber($vCur) And StringCompare($vTmp, $vCur) >= 0) Then ExitLoop
                    $aArray[$j + 1] = $vCur
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($vTmp, $aArray[$j]) >= 0) Then ExitLoop
                    $aArray[$j + 1] = $aArray[$j]
                Next
            EndIf
            $aArray[$j + 1] = $vTmp
        Next

EndFunc

; 2D Sort helper functions

; Existing __ArrayQuickSort2D

Func __ArrayTagSort2D(Const ByRef $aArray, ByRef $aTrac, Const ByRef $iStep, Const ByRef $iStart, Const ByRef $iEnd, Const ByRef $iSubItem, Const ByRef $iSubMax)
    If $iEnd <= $iStart Then Return
    Local $vTmp
    ; InsertionSort (faster for smaller segments)
    If ($iEnd - $iStart) < 15 Then ; Force tagsort
        For $i = $iStart + 1 To $iEnd
            $vTmp = $aTrac[$i]

            ; Follows the same logic as __ArrayQuickSort1D
            If IsNumber($aArray[$vTmp][$iSubItem]) Then
                For $j = $i - 1 To $iStart Step -1
                    If ((($aArray[$vTmp][$iSubItem] * $iStep) >= $aArray[$aTrac[$j]][$iSubItem] * $iStep) And IsNumber($aArray[$aTrac[$j]][$iSubItem])) _
                    Or (Not IsNumber($aArray[$aTrac[$j]][$iSubItem]) And StringCompare($aArray[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            Else
                For $j = $i - 1 To $iStart Step -1
                    If (StringCompare($aArray[$vTmp][$iSubItem], $aArray[$aTrac[$j]][$iSubItem]) * $iStep >= 0) Then ExitLoop
                    $aTrac[$j + 1] = $aTrac[$j]
                Next
            EndIf

            $aTrac[$j + 1] = $vTmp
        Next
        Return
    EndIf

    ; TagSort
    Local $L = $iStart, $R = $iEnd, $vPivot = $aArray[$aTrac[Int(($iStart + $iEnd) / 2)]][$iSubItem], $bNum = IsNumber($vPivot)
    Do
        If $bNum Then
            While ($iStep * ($aArray[$aTrac[$L]][$iSubItem] - $vPivot) < 0 And IsNumber($aArray[$aTrac[$L]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$L]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * ($aArray[$aTrac[$R]][$iSubItem] - $vPivot) > 0 And IsNumber($aArray[$aTrac[$R]][$iSubItem])) Or (Not IsNumber($aArray[$aTrac[$R]][$iSubItem]) And $iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        Else
            While ($iStep * StringCompare($aArray[$aTrac[$L]][$iSubItem], $vPivot) < 0)
                $L += 1
            WEnd
            While ($iStep * StringCompare($aArray[$aTrac[$R]][$iSubItem], $vPivot) > 0)
                $R -= 1
            WEnd
        EndIf
        If $L <= $R Then ; Swap
            $vTmp = $aTrac[$L]
            $aTrac[$L] = $aTrac[$R]
            $aTrac[$R] = $vTmp
            $L += 1
            $R -= 1
        EndIf
    Until $L > $R
    __ArrayTagSort2D($aArray, $aTrac, $iStep, $iStart, $R, $iSubItem, $iSubMax)
    __ArrayTagSort2D($aArray, $aTrac, $iStep, $L, $iEnd, $iSubItem, $iSubMax)
EndFunc   ;==>__ArrayTagSort2D

Func __ArrayTagSort2D_SwapSeq(ByRef $aArray, ByRef $aTrac, Const ByRef $iStart, Const ByRef $iEnd)
    Local $iCols = UBound($aArray, 2), $aFirst[$iCols], $i, $iNext

    For $iInit = $iStart To $iEnd ; initialize each potential overwrite sequence [separate closed system]
        If $aTrac[$iInit] <> $iInit Then ; rows will now be overwritten in accordance with tracking information
            $i = $iInit ; set the current row as the start of the sequence
            For $j = 0 To $iCols -1
                $aFirst[$j] = $aArray[$i][$j] ; copy the first row [although we don't know where to put it yet]
            Next
            Do
                For $j = 0 To $iCols -1
                    $aArray[$i][$j] = $aArray[$aTrac[$i]][$j] ; overwrite each row [following the trail]
                Next
                $iNext = $aTrac[$i] ; get the index of the next row in the sequence
                $aTrac[$i] = $i ; set to ignore rows already processed [may be needed once, or not at all]
                $i = $iNext ; follow the trail as far as it goes [indices could be higher or lower]
            Until $aTrac[$i] = $iInit ; all tracking sequences end at this juncture
            For $j = 0 To $iCols -1
                $aArray[$i][$j] = $aFirst[$j] ; now we know where to put the initial row we copied earlier
            Next
            $aTrac[$i] = $i ; set to ignore rows already processed [as above]
        EndIf
    Next
EndFunc ;==> __ArrayTagSort2D_SwapSeq

Edited February 6, 2018 by czardas

jpm · February 6, 2018

If I understand well no improvement if no $iAlternate

Just can be use on 2D array

Init : WorkingSet = 14168 Kb

ReDim00 : WorkingSet = 14176 Kb
ReDim : WorkingSet = 79720 Kb
Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0 : WorkingSet = 1533640 Kb
106.995 Sec : _ArraySort($aArray2D, 0, 0, 0, 0) : WorkingSet = 2391728 Kb @error=0
106.071 Sec : _ArraySort_NEW($aArray2D, 0, 0, 1, 0) : WorkingSet = 2391728 Kb @error=0
Ratio = 1
0 Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 1565324 Kb @error=6
26.903 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 1, 1) : WorkingSet = 2398312 Kb @error=0
Ratio = 0
Reset : WorkingSet = 2398312 Kb

I don't fully understand why the test comparison is not done on the initial generated array when using the proposed implementation

If using the initial generation incase of test 8 it does not improve so much

ReDim00 : WorkingSet = 1572416 Kb
ReDim : WorkingSet = 1637956 Kb
Test # 8 : Rows = 8388608 : Columns = 2 : Penalty = 0 : WorkingSet = 1061716 Kb
1123.279 Sec : _ArraySort($aArray2D, 0, 0, 0, 0) : WorkingSet = 1838064 Kb @error=0
1128.007 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 0) : WorkingSet = 1837064 Kb @error=0
Ratio = 1
0 Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 1353336 Kb @error=6
976.487 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 1964852 Kb @error=0
Ratio = 0
Reset : WorkingSet = 1367368 Kb

here my test used with the #52 proposal

;~ #AutoIt3Wrapper_UseX64=y
#include <_ArraySort_New.au3>

#cs ----------------------------------------------------------------------------

 AutoIt Version: 3.3.14.3
 Author:         myName

 Script Function:
    Template AutoIt script.

#ce  ----------------------------------------------------------------------------

; Script Start - Add your code below here

#include <Array.au3>
#include <WinAPIProc.au3>

Local $bRestoreInitial = False
;~ Local $bRunNoPivot = False

;~ Local $bRestoreInitial = True
Local $bRunNoPivot = True

ConsoleWrite( ">>>>>>>>>>>> Restore Initial genetation = " & $bRestoreInitial & @CRLF)
ConsoleWrite( ">>>>>>>>>>>> Run No Pivot = " & $bRunNoPivot & @CRLF & @CRLF)

Global $iPenalty = 0 ; Caution: 1 penalty point = between 8 and 16 megabytes depending on the test number
Global $iFirstTest = 1 ; lowest test number = 1
Global $iLastTest = 1 ; highest test number = 8

; the following sleep values can be modified depending on available RAM
Global $iNap = 00000 ; 30 secs - short sleep
Global $iSleep = 00000 ; 40 secs - long sleep to be multiplied by the test number because each test becomes more brutal

; Bounds for 2D arrays containing 16777216 elements [Rows, Columns]
Global $aArray[0][0], $aArray2D_sav, $aArray2D = $aArray, $aBounds = [['', ''], [512, 32768], [1024, 16384], [2048, 8192], [4096, 4096], [8192, 2048], [16384, 1024], [32768, 512], [8388608, 2]]
;~ Global $aArray[0][0], $aArray2D = $aArray, $aBounds = [['',''],[512,16384],[1024,8192],[2048,4096],[4096,2048],[8192,1024],[16384,512],[32768,2],[8388608, 1]]
Local $iError, $iTimer, $fTimer0, $fTimer1, $fTimer2, $fTimer3
Global $sBloat = StringFormat("%0" & $iPenalty & "s", "")

Local $aData = _WinAPI_GetProcessMemoryInfo()
ConsoleWrite("Init : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF & @CRLF)
;~ Int($aData[2] / 1024)

Local $iSecondCol = 1
If $bRestoreInitial Then $iSecondCol = 0

For $iTestNum = $iFirstTest To $iLastTest
    ReDim $aArray2D[0][0] ; get rid of all previous data [COM ERROR HERE ON 1ST REPEAT ==> see line 36 below]
    $aData = _WinAPI_GetProcessMemoryInfo()
    ConsoleWrite("ReDim00 : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF)

    ReDim $aArray2D[$aBounds[$iTestNum][0]][$aBounds[$iTestNum][1]] ; resize the array
    $aData = _WinAPI_GetProcessMemoryInfo()
    ConsoleWrite("ReDim : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF)
    GenerateHorribleData($aArray2D) ; the first two columns are filled with random strings and numbers
    AddMoreBloat($aArray2D) ; the rest array is filled with the same string duplicated again and again
    Sleep($iNap)

;~  _ArrayDisplay($aArray2D, "$aArray2D Initial", "0:1000|0:" & $iSecondCol)

    $aArray2D_sav = $aArray2D

    $aData = _WinAPI_GetProcessMemoryInfo()
    ConsoleWrite("Test # " & $iTestNum & " : Rows = " & UBound($aArray2D) & " : Columns = " & UBound($aArray2D, 2) & " : Penalty = " & $iPenalty & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF)

    ; now we are ready to run tests
    If $bRunNoPivot Then
        $iTimer = TimerInit()
        ; for the 1st test, sort on the first column
        _ArraySort($aArray2D, 0, 0, 0, 0)
        $iError = @error
        $fTimer0 = Round(TimerDiff($iTimer) / 1000, 3)
        $aData = _WinAPI_GetProcessMemoryInfo()
        ConsoleWrite($fTimer0 & " Sec : _ArraySort($aArray2D, 0, 0, 0, 0)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF)
;~     Sleep($iSleep * $iTestNum) ; multiplied by the test number because each test becomes more brutal

        If $bRestoreInitial Then $aArray2D = $aArray2D_sav

        $iTimer = TimerInit()
        ; sort similar data on the second column
        _ArraySort_NEW($aArray2D, 0, 0, 0, $iSecondCol) ; the more rows, the more similar the starting conditions [lost after the 1st sort]
        $iError = @error
        $fTimer1 = Round(TimerDiff($iTimer) / 1000, 3)
        $aData = _WinAPI_GetProcessMemoryInfo()
        ConsoleWrite($fTimer1 & " Sec : _ArraySort_NEW($aArray2D, 0, 0, " & $iSecondCol & ", 0)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF)

        ConsoleWrite("Ratio = " & Round($fTimer0 / $fTimer1, 1) & @CRLF)
    EndIf

    ; Check $iPivot/$iAlternate
    $aArray2D = $aArray2D_sav ; Restore initial generation

    $iTimer = TimerInit()
    ; for the 1st test, sort on the first column
    _ArraySort($aArray2D, 0, 0, 0, 0, 1) ; the more rows, the more similar the starting conditions [lost after the 1st sort]
    $iError = @error
    $fTimer2 = Round(TimerDiff($iTimer) / 1000, 3)
    $aData = _WinAPI_GetProcessMemoryInfo()
    ConsoleWrite($fTimer2 & " Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF)

    $aArray2D = $aArray2D_sav

    $iTimer = TimerInit()
    ; sort similar data on the second column
    _ArraySort_NEW($aArray2D, 0, 0, 0, $iSecondCol, 1) ; the more rows, the more similar the starting conditions [lost after the 1st sort]
    $iError = @error
    $fTimer3 = Round(TimerDiff($iTimer) / 1000, 3)
    $aData = _WinAPI_GetProcessMemoryInfo()
    ConsoleWrite($fTimer3 & " Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, " & $iSecondCol & ", 1)" & " : WorkingSet = " & Int($aData[2] / 1024) & " Kb @error=" & $iError & @CRLF)

    ConsoleWrite("Ratio = " & Round($fTimer2 / $fTimer3, 1) & @CRLF)

;~  If $iTestNum = $iLastTest Then _ArrayDisplay($aArray2D, "$aArray2D Last", "0:1000|0:" & $iSecondCol)

;~  $aArray2D = $aArray ; patch to deal with the COM error above ??? Jpm:I don't really understand the impact <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

;~     Sleep($iSleep * $iTestNum)
    Sleep($iNap)
    $aData = _WinAPI_GetProcessMemoryInfo()
    ConsoleWrite("Reset : WorkingSet = " & Int($aData[2] / 1024) & " Kb" & @CRLF & @CRLF)
    $iTestNum = 2 * $iTestNum - 1 ; for 1 2 4 8 only testing
Next

Func GenerateHorribleData(ByRef $aArray2D)
    If Not IsArray($aArray2D) Or UBound($aArray2D, 0) <> 2 Or UBound($aArray2D) < 2 Or UBound($aArray2D, 2) < 2 Then Return SetError(1)

    ; strings of 4 characters selected from 95 available characters would generate enough permutations to fill an array with 16777216 elements
    ; so I guess 3 characters will suffice
    Local $iCount = 0, $aCombi[1714750] ; 2 * 95 ^ 3

    ; create 857375 unique strings
    For $i = 32 To 126 ; use ascii range 126 - 31 = 95 characters
        For $j = 32 To 126
            For $k = 32 To 126
                $aCombi[$iCount] = $sBloat & Chr($i) & Chr($j) & Chr($k)
                $iCount += 1
            Next
        Next
    Next

    ; add another 857375 integers - exactly the same number as strings
    For $i = 857375 To 1714749
        $aCombi[$i] = $i
    Next

    _ArrayShuffle($aCombi) ; generate a random sample of 1714750 unique values
    For $i = 0 To UBound($aArray2D) - 1
        $aArray2D[$i][0] = $aCombi[Mod($i, 1714750)]
    Next

    _ArrayShuffle($aCombi) ; generate a similar random sample of 1714750 unique values
    For $i = 0 To UBound($aArray2D) - 1
        $aArray2D[$i][1] = $aCombi[Mod($i, 1714750)]
    Next
    ;_ArrayDisplay($aCombi, "Combi", '857000:857374')
EndFunc   ;==>GenerateHorribleData

Func AddMoreBloat(ByRef $aArray2D)
    Local $sMoreBloat = $sBloat & "str"
    If Not IsArray($aArray2D) Or UBound($aArray2D, 0) <> 2 Or UBound($aArray2D) < 2 Or UBound($aArray2D, 2) < 2 Then Return SetError(1)
    For $i = 0 To UBound($aArray2D) - 1
        For $j = 2 To UBound($aArray2D, 2) - 1
            $aArray2D[$i][$j] = $sMoreBloat
        Next
    Next
EndFunc   ;==>AddMoreBloat

Cheers

iamtheky · February 6, 2018

@czardas

post #52 might be the single biggest boner for sorting arrays anyone has ever exhibited

czardas · February 6, 2018

41 minutes ago, jpm said:

If I understand well no improvement if no $iAlternate

Just can be use on 2D array

Both statements are correct.

43 minutes ago, jpm said:

I don't fully understand why the test comparison is not done on the initial generated array when using the proposed implementation

If using the initial generation incase of test 8 it does not improve so much

1. I thought that generating the initial array, with so many calls to Random(), was taking too much time and recreating the exact same starting conditions (in a test that I could post on the forum) seemed difficult to me at the time.

2. This is to be expected. Two columns is unlikely to make much difference and may even be slightly slower depending on bloat within the array.

I will try your new test and report back later. Thanks!

Melba23 · February 6, 2018

12 hours ago, czardas said:

This bug appears to have been introduced with changes made by Melba23

Mea culpa.

M23

czardas · February 6, 2018

No pasa nada!

czardas · February 6, 2018

Results for jpm's test:

Init : WorkingSet = 9084 Kb

ReDim00 : WorkingSet = 9096 Kb
ReDim : WorkingSet = 74768 Kb
Test # 1 : Rows = 512 : Columns = 32768 : Penalty = 0 : WorkingSet = 117208 Kb
170.311 Sec : _ArraySort($aArray2D, 0, 0, 0, 0) : WorkingSet = 1339188 Kb @error=0
178.93 Sec : _ArraySort_NEW($aArray2D, 0, 0, 1, 0) : WorkingSet = 1363056 Kb @error=0
Ratio = 1
0.059 Sec : _ArraySort($aArray2D, 0, 0, 0, 0, 1) : WorkingSet = 50196 Kb @error=6
47.39 Sec : _ArraySort_NEW($aArray2D, 0, 0, 0, 1, 1) : WorkingSet = 1392908 Kb @error=0
Ratio = 0
Reset : WorkingSet = 1291008 Kb

+>15:48:45 AutoIt3.exe ended.rc:0

This computer is not ideal for stress testing.

jpm · February 6, 2018

So I am happy that I understand.

Cheers

czardas · February 6, 2018

@Melba23 Your input/code has been very helpful and it didn't take long to track where the previous code was failing. The TagSort option can easily be removed if it doesn't stand the test of time. I would not commit it to the main release just yet. I would be very happy to see it tested in a beta release though.

Optimized _ArraySort

Recommended Posts

Link to comment

Share on other sites

Top Posters In This Topic

Top Posters In This Topic

Popular Posts

czardas

czardas

iamtheky

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Create an account or sign in to comment

Create an account

Sign in

Recently Browsing 0 members