FWIW，这是对最初关于让合并排序代码工作的问题的回答。不幸的是，它的性能不是很好，所以我不知道它是否真的能帮助你解决1 M+行的排序问题。
好消息
我对你原来的mergeSort做了一些调整，似乎可以修复它，至少对于你问题顶部的示例数组是这样。
修复的大部分是错别字-请参阅BeyondCompare的屏幕截图，看看我所做的更改：

坏消息

很慢。

PS> $array = [string[]] (1..10000 | % { $_.ToString() }) 
PS> measure-command {
    mergeSort $array
}

...
TotalMilliseconds : 11511.74

相比

PS> $array = [string[]] (1..10000 | % { $_.ToString() }) 
PS> measure-command {
    $array = $array | sort-object
}

...
TotalMilliseconds : 36.8607

也许它在你所说的数据规模下表现得更好，但我没有耐心测试它：-）
丑八怪
我还稍微调整了代码，以便在对右侧执行任何操作之前对左侧进行排序，这意味着它不需要使用太多内存。
这是更新后的样本，供后人参考。

$ErrorActionPreference = "Stop";
Set-StrictMode -Version "Latest";

function mergeSort
{

    param([string[]] $arr)

    if( $arr.length -gt 1 )
    {

        # sort the left side
        $left_len = [Math]::Floor([int32]$arr.length / 2)
        $left = [string[]]::new($left_len);                                                                 
        for( $i = 0; $i -lt $left_len; $i++ )
        {
            $left[$i] = $arr[$i]
        }
        mergeSort -arr $left

        # sort the right side
        $right_len = $arr.Length - $left_len
        $right = [string[]]::new($right_len);
        for( $i = 0; $i -lt $right_len; $i++ )
        {
            $right[$i] = $arr[$left_len + $i]
        }
        mergeSort -arr $right

        # merge the two sides
        merge -result $arr -left $left -right $right

    }

}

function merge
{
    param ([string[]] $result,[string[]] $left, [string[]] $right)

    $i1 = 0
    $i2 = 0

    for ($i = 0; $i -lt $result.Length; $i++)
    {
        if( ($i1 -lt $left.Length) -and (($i2 -ge $right.Length) -or $left[$i1].CompareTo($right[$i2]) -lt 0) )
        {
            $result[$i] = $left[$i1]
            $i1++
        }
        else
        {
            $result[$i] = $right[$i2]
            $i2++
        }
    }

}

$array = [string[]] @("Ryan", "Kelly", "Alex", "Kyle", "Riley")
mergeSort $array

write-host $array

需要特别调用的一件事是将输入数组转换为字符串：

$array = [string[]] @("Ryan", "Kelly", "Alex", "Kyle", "Riley")

如果没有强制转换，$array的类型是[System.Object[]]，发生的情况是PowerShell将在内部创建一个新的 * 临时 * [string[]]数组，将值复制到其中，然后对内部数组进行排序，但它 * 不会 * 将内部数组分配回$array。
不戴石膏试试看。

使用一个排序的字典，它的关键字是hash

$filename = 'c:\temp\test.csv'
$dict = [System.Collections.Generic.SortedDictionary[string,string]]::new()

$reader = [System.IO.StreamReader]::new($filename)
#skip header
$reader.ReadLine()
while( ($line = $reader.ReadLine()) -ne $null )
{
   if($line.Length.Trim() > 0)
   {
      $firstComma = $line.IndexOf(',')
      $id = $line.Substring(0, $firstComma)
      $dict.Add($id, $line)
   }
}
$dict

如果您在使用PowerShell时确实遇到了性能问题，则可以从阅读PowerShell scripting performance considerations开始

自顶向下实现

关于你的第一次尝试，你可能想要避免的一件事是递归函数，因为在PowerShell中调用函数是非常昂贵的，请参阅：What is the best way to reuse static code
特定错误脚本由于调用深度溢出而失败很可能是由于错误的检查，您应该停止递归调用，因此永远继续...

自底向上实现

关于你的第二次尝试，使用增加赋值运算符（+=）来创建一个集合是一个很常见的PowerShell性能问题，请参阅：Why should I avoid using the increase assignment operator ( += ) to create a collection

合并排序原型

考虑到这两个问题，你可能会得到一个像这样的函数：

function MergeSort($List, $By) {
    $Count = @($List).get_Count()
    if ($Count -le 1) { return $List }
    $Temp = New-Object PSCustomObject[] $Count
    for ($Width = 1; $Width -lt $Count; $Width = 2 * $Width) {
        for ($Start = 0; $Start -lt $Count; $Start = $Start + 2 * $Width) {
            $Left = $Right = $To = 0
            do {
                if (
                  $Right -ge $Width -or $Start + $Width + $Right -ge $Count -or (
                    $Left -lt $Width -and $Start + $Left -lt $Count -and 
                    $List[$Start + $Left].$By -lt $List[$Start + $Width + $Right].$By
                  )
                )    { $Temp[$Start + $To++] = $List[$Start + $Left++] }
                else { $Temp[$Start + $To++] = $List[$Start + $Width + $Right++] }
            } while ($To -lt 2 * $Width -and $Start + $To -lt $Count)
        }
        $List, $Temp = $Temp, $List # Swap (the references of) the lists
    }
    $List
}

Demo

$Data = ConvertFrom-Csv @'
id,firstname,lastname,email,email2,profession
100,Andeee,Michella,Andeee.Michella@yopmail.com,Andeee.Michella@gmail.com,police officer
101,Tybie,1Grobe,Tybie.Grobe@yopmail.com,Tybie.Grobe@gmail.com,worker
102,Fernande,Azeria,Fernande.Azeria@yopmail.com,Fernande.Azeria@gmail.com,developer
103,Lenna,Schenck,Lenna.Schenck@yopmail.com,Lenna.Schenck@gmail.com,police officer
104,4Marti,Brittani,Marti.Brittani@yopmail.com,Marti.Brittani@gmail.com,worker
105,Riannon,Aldric,Riannon.Aldric@yopmail.com,Riannon.Aldric@gmail.com,doctor
106,Corry,Nikaniki,Corry.Nikaniki@yopmail.com,Corry.Nikaniki@gmail.com,worker
107,Correy,Shama,Correy.Shama@yopmail.com,Correy.Shama@gmail.com,police officer
108,Marcy,Drus,Marcy.Drus@yopmail.com,Marcy.Drus@gmail.com,worker
109,Bill,Valerio,Bill.Valerio@yopmail.com,Bill.Valerio@gmail.com,worker
'@

MergeSort $Data -by lastname |Format-Table

id  firstname lastname email                       email2                    profession
--  --------- -------- -----                       ------                    ----------
101 Tybie     1Grobe   Tybie.Grobe@yopmail.com     Tybie.Grobe@gmail.com     worker
105 Riannon   Aldric   Riannon.Aldric@yopmail.com  Riannon.Aldric@gmail.com  doctor
102 Fernande  Azeria   Fernande.Azeria@yopmail.com Fernande.Azeria@gmail.com developer
104 4Marti    Brittani Marti.Brittani@yopmail.com  Marti.Brittani@gmail.com  worker
108 Marcy     Drus     Marcy.Drus@yopmail.com      Marcy.Drus@gmail.com      worker
100 Andeee    Michella Andeee.Michella@yopmail.com Andeee.Michella@gmail.com police officer
106 Corry     Nikaniki Corry.Nikaniki@yopmail.com  Corry.Nikaniki@gmail.com  worker
103 Lenna     Schenck  Lenna.Schenck@yopmail.com   Lenna.Schenck@gmail.com   police officer
107 Correy    Shama    Correy.Shama@yopmail.com    Correy.Shama@gmail.com    police officer
109 Bill      Valerio  Bill.Valerio@yopmail.com    Bill.Valerio@gmail.com    worker

但是正如在@mclaytonhelpful answer中已经得出的结论，您不太可能用自制的PowerShell函数击败原生Sort-Object。

排序字典

无论如何，@jdwenghelpful answer中提到的使用SortedDictionary<TKey,TValue> Class的建议是击败原生Sort-Object命令的更好候选。

$Dictionary = [System.Collections.Generic.SortedDictionary[string,object]]::new()
$Data.foreach{ $Dictionary[$_.lastname] = $_ }
$Dictionary.Values |Format-Table

基准测试

我质疑你关于SortedDictionary“solution is linear”的评论，但我无法证明这一点。不管怎么说，我想最终还是要看实际的表现。

$Data = 1..10000 |Foreach-Object { [PSCustomObject]@{ Id = $_; Name = (New-Guid).Guid } }

(Measure-Command { 
    $Dict = [System.Collections.Generic.SortedDictionary[string,object]]::new()
    $Data.foreach{ $Dict[$_.Name] = $_ }
    $Null = $Dict.Values
}).TotalMilliseconds

(Measure-Command { 
    $SortedList = [System.Collections.Generic.SortedList[string,object]]::new()
    $Data.foreach{ $SortedList.Add($_.Name, $_ ) }
    $Null = $SortedList.Values
}).TotalMilliseconds

(Measure-Command { 
    $Null = $Data |Sort-Object -Property Name
}).TotalMilliseconds

(Measure-Command { 
    $Null = MergeSort $Data -By Name
}).TotalMilliseconds

结果

SortedDictionary:   110.8943
SortedList:         133.1337
Sort-Object:        141.4514
MergeSort Function: 550.4682

分治

所以，现在我们知道SortedDictionary和SortedList执行得最好，让我们看看是否可以将这些.Net任务划分到多个并行线程（CPU）上。

并行排序原型

为此，我将需要SortedList（这是一个有点慢SortedDictionary），因为我将需要能够索引到返回的列表。

function ParallelSort($List, $By, $ThrottleLimit = 3) {
    $Count = $Data.get_Count()
    $Size = [Math]::Ceiling($Count / $ThrottleLimit)
    $Lists = 
        for ($c = 0; $c -lt $ThrottleLimit; $c++) {
            $Start = $c * $Size
            $End = [Math]::Min(($Start + $Size), $Count) - 1
            ,$Data[$Start..$End]
        }
    $Lists = $Lists |Foreach-Object -ThrottleLimit $ThrottleLimit -Parallel {
        $List = [System.Collections.Generic.SortedList[string,object]]::new()
        foreach ($Item in $_) { $List.Add($Item.Name, $Item ) }
        ,$List.Values
    }

    $Indices = [UInt[]]::new($ThrottleLimit)
    Do {
        $lt = $Null
        for ($l = 0; $l -lt $ThrottleLimit; $l++) {
            if ($Indices[$l] -lt $Lists[$l].Count -and (
                $Null -eq $lt -or
                $Lists[$l][$Indices[$l]].$By -lt $Lists[$lt][$Indices[$lt]].$By)
            ) { $lt = $l }
        }
        if ($Null -ne $lt) { $Lists[$lt][$Indices[$lt]++] }
    } While ($Null -ne $lt)
}

用法（健全性检查）

$Data = 1..50 |Foreach-Object { [PSCustomObject]@{ Id = $_; Name = (New-Guid).Guid } }
ParallelSort $Data -By Name

其中大量数据（例如200.000条目），合并并行排序例程确实看起来比单个进程SortedDictionary更快：

Merged-parallel:  4324.5299
SortedDictionary: 5335.0125