A mergesort implementation to sort an array without using conventional functions.

mergesort.R

"
A mergesort implementation to sort an array without using conventional functions.

This algorithm has 2 stages:
- divides the array into a list of sublists where each sublist has just 1 number.
- then merge bottom-up until it outputs the sorted array.

These videos explain everything you need to know about mergesort:
- https://class.coursera.org/algo-003/lecture/1
- https://class.coursera.org/algo-003/lecture/2
- https://class.coursera.org/algo-003/lecture/3
"

do_merge <- function(vect1, vect2) {
  "
  Does the merge step of the mergesort algorithm. 
  Merges two sorted arrays and outputs the sorted array.
  "
  
  # Deals with the cases when vect1 or vect2 is null
  if (is.null(vect1)) return(vect2)
  if (is.null(vect2)) return(vect1)
  
  # Creates a tmp array that stores the sorted results
  tmp <- array(0, length(vect1) + length(vect2))
  
  # Merges the two arrays until min(length(vect1), length(vect1))
  i <- j <- 1
  for (k in 1:length(tmp)) {
    cond <- i <= length(vect1) & j <= length(vect2)
    if (vect1[i] <= vect2[j] & cond) {
      tmp[k] <- vect1[i]
      i <- i + 1
    } else if (vect1[i] > vect2[j] & cond) {
      tmp[k] <- vect2[j]
      j <- j + 1
    }
  }
  
  # Deals with the end cases if vect1 and vect2 differ in length
  if (i > length(vect1)) {
    tmp[(i + j - 1):length(tmp)] <- vect2[j:length(vect2)]
  } else {
    tmp[(i + j - 1):length(tmp)] <- vect1[i:length(vect1)]
  }
  return(tmp)
}

# Creates an unsorted array of integers
vect <- sample(21)

# Transforms vect into a list of sublists where each sublist is sorted
vect_list <- sapply(1:length(vect), function(k) list(vect[k]))

# Merges iteratively until it outputs a sorted array
# There are faster ways (parallel merging, etc)
sorted_vect <- NULL
for (sublist_idx in 1:length(vect)) {
  sorted_vect <- do_merge(sorted_vect, as.numeric(vect_list[[sublist_idx]]))
}

vect
sorted_vect