Wednesday, October 12, 2011

PowerShell: Merge Sort

Merge Sort is an sorting algorithm in 1945 by John von Neumann. It's complexity is O(n log n), also called linearithmic (it's a product of the linear term n, and the logarithmic log n).

Function MergeSort($arrArray) {
#Write-Host "MergeSort("$arrArray")"
  if ($arrArray.length -le 1) {
    return $arrArray
  }
  $arrLeft = @()
  $arrRight = @()
  $arrResult = @()
  [int]$middle = $arrArray.length / 2
  for ($i = 0;$i -lt $middle;$i++) {
    $arrLeft += $arrArray[$i]
  }
  for ($i = $middle;$i -le ($arrArray.length-1);$i++) {
    $arrRight += $arrArray[$i]
  }
  $arrLeft = MergeSort($arrLeft)
  $arrRight = MergeSort($arrRight)
  MergeFunction $arrLeft $arrRight
}

Function MergeFunction([int[]]$arrLeft, [int[]]$arrRight) {
#Write-Host "merge2("$arrLeft", "$arrRight")"
  $arrResult = @()
  while ($arrLeft.length -gt 0 -or $arrRight.length -gt 0)   {
    If ($arrLeft.length -gt 0 -and $arrRight.length -gt 0) {
      If ($arrLeft[0] -le $arrRight[0]) {
        $arrResult += $arrLeft[0]
        If ($arrLeft.length -eq 1) {
          $arrLeft = @()
        }
        Else {
          $arrLeft = $arrLeft[1..($arrLeft.length - 1)]
        }
      }
      Else {
        $arrResult += $arrRight[0]
        If ($arrRight.length -eq 1) {
          $arrRight = @()
        }
        Else {
          $arrRight = $arrRight[1..($arrRight.length - 1)]
        }
      }
    }
    ElseIf ($arrLeft.length -gt 0) {
      $arrResult += $arrLeft[0]
      If ($arrLeft.length -eq 1) {
        $arrLeft = @()
      }
      Else {
        $arrLeft = $arrLeft[1..($arrLeft.length - 1)]
      }
    }
    ElseIf ($arrRight.length -gt 0) {
      $arrResult += $arrRight[0]
      If ($arrRight.length -eq 1) {
        $arrRight = @()
      }
      Else {
        $arrRight = $arrRight[1..($arrRight.length - 1)]
      }
    }
  }
  $arrResult
}

No comments: