nu_scripts/modules/recursion/merge.nu

# merge 2 sorted lists

# Merge 2 sorted lists
def merge-2 [l: list, r: list]: nothing -> list {
  mut ol = []
mut lprime = $l; mut rprime = $r
  let mx = ($l | length) + ($r | length)
  #print -e $"l: ($l), r: ($r)"
  while ($ol | length) < $mx {
  if ($lprime | is-empty) or ($rprime | is-empty) { break }
    if $lprime.0 <= $rprime.0 {

      $ol = ($ol | append $lprime.0)
      $lprime = ($lprime | skip)
    } else {
      $ol = ($ol | append $rprime.0)
    $rprime = ($rprime | skip)
    }
  }
  $ol | append $lprime | append $rprime
}


# Merge sort a list
# This version is non tail call optimized and might blow the stack for
# large lists.
def sort-nontail [x: list]: nothing -> list {
  let $n = ($x | length)
 let n_2: int = $n // 2

  if $n <= 1 {
    $x
  } else {
    merge-2 (sort-nontail ($x | first $n_2)) (sort-nontail ($x | skip $n_2))
  }
}