[R] Merge sort

Gaston dpv at gmx.ch
Tue Apr 19 21:39:33 CEST 2016

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,



	[[alternative HTML version deleted]]

More information about the R-help mailing list