Top-down design function triggers an infinite loop in R

Viewed 23

I am writing a function mergesort(x, decreasing = c("T", "F")) to practice the topdown design. I know that adding a default value of decreasing would solve my situation. But I don't understand why I would encounter the problem. Here are the codes:

x <- c(4, 6, 2, 3, 5, 7, 6, 4)

mergesort <- function (x, decreasing) {
  if (len < 2) {
    result <- x
  } else if (decreasing == T){
    len <- length(x)
    y <- x[1:(len %/% 2)]
    z <- x[(len %/% 2 + 1):len]
    y <- mergesort(y, T)
    z <- mergesort(z, T)
    result <- c()
    while (min(length(y), length(z)) > 0) {
      if (y[1] > z[1]) {
        result <- c(result, y[1])
        y <- y[-1]
      } else {
        result <- c(result, z[1])
        z <- z[-1]
      }
    }
    if (length(y) > 0){
      result <- c(result, y)
      }else{
        result <- c(result, z)
      }
    } else if (decreasing == F){
      len <- length(x)
      y <- x[1:(len %/% 2)]
      z <- x[(len %/% 2 + 1):len]
      y <- mergesort(y, F)
      z <- mergesort(z, F)
      result <- c()
      while (min(length(y), length(z)) > 0) {
        if (y[1] < z[1]) {
          result <- c(result, y[1])
          y <- y[-1]
        } else {
          result <- c(result, z[1])
          z <- z[-1]
        }
      }
      if (length(y) > 0){
        result <- c(result, y)
      }else{
        result <- c(result, z)
      }
    }
  return(result)
}

Why there is an error of:

> mergesort(x, F)
Error: node stack overflow
Error during wrapup: node stack overflow
Error: no more error handlers available (recursive errors?); invoking 'abort' restart
> mergesort(x, T)
Error: node stack overflow
Error during wrapup: node stack overflow
Error: no more error handlers available (recursive errors?); invoking 'abort' restart

I know the error means an infinite loop. I don't understand why the codes can trigger an infinite loop because eventually the len (length) should be less than 2 after multiple steps. Please advise. Thanks!

0 Answers
Related