Skip to content

Instantly share code, notes, and snippets.

@rebordao
Last active August 29, 2015 14:13
Show Gist options
  • Save rebordao/b0b32ae461c3c089d525 to your computer and use it in GitHub Desktop.
Save rebordao/b0b32ae461c3c089d525 to your computer and use it in GitHub Desktop.
A mergesort implementation to sort an array without using conventional functions.
"
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment