A Variation of Selection Sort

Selection sort is often considered to be one of the worse sorts, because every sorting of one element requires iteration over the entire set of data.This is only the case when the structure that the data is in does not implicitly contain information about the rank of the data.

Below, I outline a procedure to create a simple matrix which contains information about the rank of each element and allows the creation of such a matrix in O(log n) time, and the selection of an element from it can be done in O(log n) time, but tends towards constant time for first or last elements.

Create a matrix of sqrt(N) x sqrt(N) size

Firstly, considering the dimensions of the matrix, it should be as close to a square as possible, thus, every row/col should be nˆ1/2 length, to make operations across row and columns close to equivalent. Copy all the elements unsorted into the matrix.

Sort every row of the matrix

Then, sort every row of the matrix. This could be done recursively, or using something like quicksort. Considering that each of these rows is independent of the other, this can be easily parallelized. If an efficient sorting algorithm was used, the time to sort all rows would be n rows * O(log n) sort time so it would be nlogn .

Transpose the matrix

Transpose the matrix so that we can run the next operation more efficiently. This generally takes O(n) .

Sort every column(now rows) of the matrix again

This is the same case as above and thus takes the same amount of time.

Sort every diagonal with the top left being the start of the resultant sorted array

This is a similar case to sorting rows, but diagonals are of variable length, and there are 2 log(n)+1 diagonals. This can also be parallelized, and the difference in length should be considered when thinking of how to sort them.

The resultant matrix is thus sorted such that the top left half of any submatrix is greater than the bottom right half. In addition, we are guaranteed to get the highest element in the “exposed” part of the matrix. It can be considered that we “erode” the top left of the array in order to “expose” the largest elements. The “exposed” part is the first element of every row which has had it’s first element removed and is not empty. If we compare all of these “exposed” elements, we get the next greatest element in the array. This can also be done from the bottom right of the array to get a sort in the inverse order.

What is the time complexity of this operation? Since we must select every element, we are guaranteed at least O(n) time complexity. For every element, there must be however many elements in its diagonal that must be checked which is log(n) . This is also efficient if we want to select just the first few elements.

Streaming Data while sorting

While the matrix is being created, I have not implemented something where one can add data to it, but in theory one should be able to add individual elements to the row with the least elements if one exists, or the firstmost-row, and use binary insertion to swap places with an element in the array.

Cache hits/misses?

I have not done sufficient research into this to see how this might work for this sort. Given that we are often searching along diagonals, I suspect there will be a large number of cache misses. How can this be reconciled? Since we sort the diagonals last, it might be better to store the array back as an array of diagonals rather than its row and column form. This might involve more complicated logic for selection. One thing that is unclear is that it exhibits extreme spatial locality within the array, since the erosion has a very clear pattern.

An example implementation is provided below. This is provided in Ruby for the reader’s convenience of understanding, but it is not intended for speed in Ruby, naturally.

# assuming mx is square
def diagonals(mx)
result = []
amt = mx.length
amt.times do |x|
diag = []
start = x
until x == -1 do
diag << (mx[start-x][x])
x = x-1
end
result.push diag
end
(amt-1).times do |x|
diag = []
start = x
until x == -1 do
diag.push(mx[amt-1-x][amt-1-(start-x)])
x = x-1
end
result.push diag
end
result
end
def diagonals_to_a(diags)
len = (diags.length.next) >> 1
result = ([nil]*len*len).each_slice(len).map { |x| x }
flat_diags = diags.flatten(1)
c = 0
len.times do |x|
start = x
until x == -1 do
result[start-x][x] = flat_diags[c]
x -= 1
c += 1
end
end
len.pred.times do |x|
start = x
until x == -1 do
result[len-1-x][len-1-(start-x)] = flat_diags[c]
x -= 1
c += 1
end
end
result
end
def min(a, b)
b > a ? a : b
end
def matrix_select_sort(arr)
len = Math.sqrt(arr.length).floor
container = arr
.each_slice(len)
.map(&:sort)
.transpose
.map(&:sort)

container = diagonals(container)
.map(&:sort)
container = diagonals_to_a(container)
check_bounds = (0..1)
result = []
selected = check_bounds.begin
until check_bounds.end == len -1 do
selected = check_bounds.begin
check_bounds.each do |n|
if container[selected].first > container[n].first
(selected = n) == check_bounds.end && check_bounds = (check_bounds.begin..check_bounds.end.next)
end
end

result.push(container[selected].shift)
container[check_bounds.begin].length == 0 && check_bounds = (check_bounds.begin.next..check_bounds.end)
end
until check_bounds.begin == len -1 do
selected = check_bounds.begin
check_bounds.each do |n|
if container[selected].first > container[n].first
selected = n
end
end

result.push(container[selected].shift)
container[check_bounds.begin].length == 0 && check_bounds = (check_bounds.begin.next..check_bounds.end)
end
result + container.last
end
module Enumerable
def sorted?
each_cons(2).all? { |a, b| (a <=> b) <= 0 }
end
end
vals = (1..(900 * 900)).to_a.shuffle
start = Time.now
p matrix_select_sort(vals).sorted?
p "matrix select", Time.now - start
startNativeSort = Time.now
vals.sort
p "native", Time.now - startNativeSort