PowerShell自定义大数组排序求助：归并排序栈溢出及并行方案报错

问题背景 #

我有一个包含100万+条目的巨型数组，元素分为字母数字混合和纯字母两种类型。数组来自外部导出的CSV文件（无法获取生成该CSV的任务代码，只能拿到结果），示例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

由于Sort-Object或原生Sort对全数组排序耗时过长，必须在PowerShell环境下实现更高效的排序。

现有代码问题分析 #

归并排序脚本的错误 #

参考Java写法的归并排序脚本出现The script failed due to call depth overflow错误，核心问题如下：

1. 递归终止条件缺失：无论数组长度是否小于2，都会执行后续递归调用，导致无限递归
2. 数组赋值逻辑错误：循环中直接用$left= $arr[$i]覆盖数组变量，未给数组元素赋值，正确写法应为$left[$i] = $arr[$i]
3. 变量名拼写错误：merge函数中$12 = 0是笔误，应为$i2 = 0；$result.legnth应为$result.length
4. 循环边界错误：merge函数的循环条件$i -le $result.Length会导致数组越界，应改为$i -lt $result.Length

修正后的归并排序脚本：

function mergeSort {
    param([string[]] $arr)

    if ($arr.Length -ge 2) {
        # 分割左右数组
        $mid = [math]::Floor($arr.Length / 2)
        $left = $arr[0..($mid-1)]
        $right = $arr[$mid..($arr.Length-1)]

        # 递归排序左右子数组
        $left = mergeSort $left
        $right = mergeSort $right

        # 合并结果
        return merge $left $right
    }
    else {
        # 递归终止：单个元素直接返回
        return $arr
    }
}

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

    $result = [string[]]::new($left.Length + $right.Length)
    $i1 = 0
    $i2 = 0
    $current = 0

    while ($i1 -lt $left.Length -and $i2 -lt $right.Length) {
        if ($left[$i1].CompareTo($right[$i2]) -lt 0) {
            $result[$current] = $left[$i1]
            $i1++
        }
        else {
            $result[$current] = $right[$i2]
            $i2++
        }
        $current++
    }

    # 处理剩余元素
    while ($i1 -lt $left.Length) {
        $result[$current] = $left[$i1]
        $i1++
        $current++
    }

    while ($i2 -lt $right.Length) {
        $result[$current] = $right[$i2]
        $i2++
        $current++
    }

    return $result
}

# 测试
$array = @("Ryan", "Kelly", "Alex", "Kyle", "Riley")
$sortedArray = mergeSort $array
$sortedArray

并行处理方案的错误 #

尝试用SortedSet实现并行排序的脚本存在以下问题：

1. SortedSet<T>类型错误：SortedSet是单泛型参数集合，不存在SortedSet<TKey, TValue>，应使用SortedSet<string>或结合字典处理索引
2. 数组分割逻辑冗余：Split-Collection后再用-join ','和Split(",")完全没必要，直接分割成数组即可
3. 并行逻辑未真正实现：当前代码只是循环添加元素，未利用PowerShell的并行能力

高效优化方案 #

方案一：使用.NET原生排序方法 #

直接调用.NET的Array.Sort方法，性能远高于PowerShell原生的Sort-Object，适合百万级数据：

# 读取CSV数据（假设读取后是对象数组，若要排序某列比如firstname）
$csvData = Import-Csv -Path "your_file.csv"

# 提取要排序的列到字符串数组
$targetArray = $csvData.firstname

# 使用.NET Array.Sort高效排序
[Array]::Sort($targetArray)

# 输出结果
$targetArray

方案二：并行归并排序（利用PowerShell Runspace） #

对于超大规模数组，可以用Runspace实现并行递归排序：

function ParallelMergeSort {
    param([string[]] $arr)

    if ($arr.Length -lt 10000) {
        # 小数据量直接用.NET排序，避免并行开销
        [Array]::Sort($arr)
        return $arr
    }

    $mid = [math]::Floor($arr.Length / 2)
    $left = $arr[0..($mid-1)]
    $right = $arr[$mid..($arr.Length-1)]

    # 创建Runspace池
    $runspacePool = [RunspaceFactory]::CreateRunspacePool(1, 2)
    $runspacePool.Open()

    # 定义左右排序的脚本块
    $leftJob = [powershell]::Create().AddScript({
        param($data)
        ParallelMergeSort $data
    }).AddArgument($left)
    $leftJob.RunspacePool = $runspacePool

    $rightJob = [powershell]::Create().AddScript({
        param($data)
        ParallelMergeSort $data
    }).AddArgument($right)
    $rightJob.RunspacePool = $runspacePool

    # 启动并行任务
    $leftHandle = $leftJob.BeginInvoke()
    $rightHandle = $rightJob.BeginInvoke()

    # 等待任务完成并获取结果
    $sortedLeft = $leftJob.EndInvoke($leftHandle)
    $sortedRight = $rightJob.EndInvoke($rightHandle)

    # 清理资源
    $leftJob.Dispose()
    $rightJob.Dispose()
    $runspacePool.Close()
    $runspacePool.Dispose()

    # 合并结果
    return Merge $sortedLeft $sortedRight
}

# 复用之前的merge函数
function Merge {
    param([string[]] $left, [string[]] $right)

    $result = [string[]]::new($left.Length + $right.Length)
    $i1 = 0
    $i2 = 0
    $current = 0

    while ($i1 -lt $left.Length -and $i2 -lt $right.Length) {
        if ($left[$i1].CompareTo($right[$i2]) -lt 0) {
            $result[$current] = $left[$i1]
            $i1++
        }
        else {
            $result[$current] = $right[$i2]
            $i2++
        }
        $current++
    }

    while ($i1 -lt $left.Length) {
        $result[$current] = $left[$i1]
        $i1++
        $current++
    }

    while ($i2 -lt $right.Length) {
        $result[$current] = $right[$i2]
        $i2++
        $current++
    }

    return $result
}

# 测试
$array = @('Ryan', 'Kelly', 'Alex', 'Kyle', 'Riley', '4test', 'test4', 'why', 'you', 'me', 'where', 'hello', 'jose', 'test', 
'Jelly', 'Plex', 'Cyle', 'Miley', '5test', '3test4', 'who', 'Bou', 'We', 'There', 'Yellow', 'Pose', 'West')
$sortedArray = ParallelMergeSort $array
$sortedArray

方案三：利用SortedSet去重+排序 #

如果不需要保留重复元素，SortedSet是高效的选择：

$array = @('Ryan', 'Kelly', 'Alex', 'Kyle', 'Riley', '4test', 'test4', 'why', 'you', 'me', 'where', 'hello', 'jose', 'test', 
'Jelly', 'Plex', 'Cyle', 'Miley', '5test', '3test4', 'who', 'Bou', 'We', 'There', 'Yellow', 'Pose', 'West')

# 创建SortedSet，自动排序
$sortedSet = [System.Collections.Generic.SortedSet[string]]::new()
foreach ($item in $array) {
    $sortedSet.Add($item) | Out-Null
}

# 转换为数组输出
$sortedArray = $sortedSet.ToArray()
$sortedArray

内容的提问来源于stack exchange，提问作者JEuvin