Powershell Sort Function Time Complexity

user_16227962 0
Viewed 137

I couldn't find this information on Microsoft's Docs for the Sort-Object cmdlet.

I am using Powershell's Sort-Object to sort objects based on a property, i.e.: $foo | Sort-Object -Property x in an Azure RunBook, what would be time complexity of this?

azure-runbook azure-powershell powershell
2 Answers

As can be seen on GitHub, Sort-Object uses List<T>.Sort() to sort the objects. And according to this SO anwser, its time complexity is O(n log n).

user_8433450

I guess you can see for yourself, just change the values on the $elements object. I think this is linear time O(n) but I'm not an expert on this.

$elements = [pscustomobject]@{
    Minimum = 100
    Maximum = 2000
    Incremental = 100
}

$testRuns = 49

for($i=$elements.minimum;$i -le $elements.maximum;$i=$i+$elements.incremental)
{
    $arr = 0..$i | ForEach-Object {
        [pscustomobject]@{
            Value = Get-Random -Maximum 1000
        }
    }

    0..$testRuns | ForEach-Object {
        Measure-Command { $arr | Sort-Object Value }
    } |
    Measure-Object TotalMilliseconds -Maximum -Average -Minimum |
    Select-Object @{n='Elements';e={$i}},Average,Maximum,Minimum
}

Output

Elements   Average Maximum Minimum
--------   ------- ------- -------
     100  0.698054  7.8588  0.3769
     200  0.893544  1.9095  0.7365
     300   1.43093  2.4781  1.1179
     400  2.052776  3.7096  1.5384
     500  2.381598  3.5417  1.9008
     600  3.277292  4.9029  2.3808
     700   3.37905  6.2258  2.6886
     800  4.177368  6.4848  3.0926
     900  4.626102  5.8873  3.5225
    1000   4.94238  6.9827  3.8871
    1100  6.062798 25.2185  4.4134
    1200  6.649458  8.4747  5.4431
    1300  7.304344 10.1546  5.9863
    1400   8.16644  11.657  6.5452
    1500  8.179668 11.9478  6.1667
    1600   9.44597 13.1438  7.0721
    1700  9.983092 12.9889  7.4455
    1800 11.246036 15.7499   8.538
    1900 11.000806 15.5332  8.3169
    2000 13.556442 24.1767  8.7538
user_153395440
Related