Merge sort

Hello everyone,

I am learning R since recently, and as a small exercise I wanted to 
write a recursive mergesort. I was extremely surprised to discover that 
my sorting, although operational, is deeply inefficient in time. Here is 
my code :

merge <- function(x,y){
  if (is.na(x[1])) return(y)
  else if (is.na(y[1])) return(x)
  else if (x[1]<y[1]) return(c(x[1],merge(x[-1],y)))
  else return(c(y[1],merge(x,y[-1])))
}

division <- function(x){
  if (is.na(x[3])) return(cbind(x[1],x[2]))
  else 
return(cbind(c(x[1],division(x[-c(1,2)])[,1]),c(x[2],division(x[-c(1,2)])[,2])))
}

mergesort <- function(x){
  if (is.na(x[2])) return(x)
  else{
    print(x)
    t=division(x)
    return(merge(mergesort(t[,1]),mergesort(t[,2])))
  }
}

I tried my best to write it "the R-way", but apparently I failed. I 
suppose some of the functions I used are quite heavy. I would be 
grateful if you could give a hint on how to change that!

I hope I made myself clear and wish you a nice day,

Cheers,

Gaston