# Sort Algorithms in Julia

Similar to this question here, I am trying to implement sort algorithms in Julia, as part of a package.

The code for the implementation is as follows:

"""
The swapping function implementation
"""
function swap!{T}(x::AbstractArray{T}, a::T, b::T)

tmp = x[a]
x[a] = x[b]
x[b] = tmp
return x

end

"""
insertsort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray
Sorts an array using the **Insertion Sort** approach.
"""
function insertsort!{T}(x::AbstractArray{T})

for index = 2:length(x)

current  = x[index]
position = index

# For sublist sorting
while position > 1 && x[position - 1] > current
x[position] = x[position - 1]
position -= 1
end

x[position] = current

end

return x
end

"""
bubblesort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray
Sorts an array using the **Bubble Sort** approach.
"""
function bubblesort!{T}(x::AbstractArray{T})

for i in 2:length(x)
for j in 1:length(x)-1
if x[j] > x[j+1]
swap!(x, j, j+1)
end
end
end

return x
end

"""
selectsort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray
Sorts an array using the **Selection Sort** approach.
"""
function selectsort!{T}(x::AbstractArray{T})

for i in 1:length(x)-1
iMin = i
for j in i+1:length(x)
if x[j] < x[iMin]
iMin = j
end
end

swap!(x, i, iMin)
end

return x
end

"""
quicksort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray
Sorts an array using the **Quick Sort** approach.
"""
function quicksort!{T}(x::AbstractArray{T}, first::T = 1, last::T = length(x))

if last > first

pivot       = x[first]
left, right = first, last

while left <= right
while x[left] < pivot
left += 1
end
while x[right] > pivot
right -= 1
end
if left <= right
swap!(x, left, right)
left += 1
right -= 1
end
end

quicksort!(x, first, right)
quicksort!(x, left, last)
end

return x
end

"""
mergesort!{T}(x::AbstractArray{T}) ↦ x::AbstractArray
Sorts an array using the **Merge Sort** approach.
"""
function mergesort!{T}(x::AbstractArray{T})

if length(x) > 1
mid    = div(length(x), 2)
left   = mergesort!(x[1:mid])
right  = mergesort!(x[mid+1:length(x)])
result = Array(eltype(left), length(left) + length(right))

k = 1

while length(left) != 0 && length(right) != 0
if left <= right
result[k] = left
left      = left[2:end]
else
result[k] = right
right = right[2:end]
end
k += 1
end

while length(left) != 0
result[k] = left
left = left[2:end]
k += 1
end

while length(right) != 0
result[k] = right
right = right[2:end]
k += 1
end

for i = 1:length(x)
x[i] = result[i]
end

end

return x
end


All the sort algorithms are in-place. Are there any ways I can make speed up the implementations along with optimizing code for performance and quality?

(The reason I created a separate swap function, rather than doing x[a], x[b] = x[b], x[a] is that I felt it'd look more neat. Need your views on that too,)

• result = Array(eltype(left), length(left) + length(right)): are you creating an array right there? Mar 8, 2016 at 8:56
• @coderodde Yes. eltype gives the Type and length(left) + length(right) gives the requisite length Mar 8, 2016 at 9:00
• For this very reason your mergesort is not in-place. Mar 8, 2016 at 9:10
• @coderodde I should confess that that was a hack to make it look like in-place :) (Would be changing a later). Mar 8, 2016 at 10:09
• Actually there exists an in-place mergesort, yet, as far as I recall, it's slower by the factor of $\Theta(\log n)$. Mar 8, 2016 at 10:31

Your mergesort has a serious issue. If you run

size=100000
x=rand(1:(2^62),size)
@time(mergesort!(x))


you will find that your algorithm is allocating ram 2.34 million times, and is allocating 37.4 GB The problem comes from this block:

while length(left) != 0 && length(right) != 0
if left <= right
result[k] = left
left      = left[2:end]
else
result[k] = right
right = right[2:end]
end
k += 1
end


If you instead write,

left_ind = 1
right_ind = 1
r_ind = 1
while left_ind<=length(left) && right_ind<=length(right)
if left[left_ind]<right[right_ind]
result[r_ind]=left[left_ind]
left_ind += 1
else
result[r_ind]=right[right_ind]
right_ind += 1
end
r_ind += 1
end
if left_ind<=length(left)
result[r_ind:end] = left[left_ind:end]
elseif right_ind<=length(right)
result[r_ind:end] = right[right_ind:end]
end
result


This drops the time from 3.7 seconds to .2 seconds, and memory allocation to 57MB

• It turns out that since you were creating n arrays when merging arrays of size n, you managed to make a version of mergesort that had runtime ~ O(n^2log(n)). Jul 28, 2016 at 23:33