Sortrows function and real-time systems

I would like to understand if sortrows is suited for real-time systems.

Is it based on a recursive algorithm?

Answer 1

[Walter Roberson]

sortrows() is based on quicksort.

quicksort() does not require that the comparison operation be literally x(idx1) < x(idx2) : quicksort as an algorithm just says that at a particular point, you invoke a comparison function that tells you the relative order of two entries given their index. The comparison operator can be, for example,

temp = sign(x(idx1, :) - x(idx2, :)) .* sort_direction_hints;
if ~any(temp)
    sort_flag = 0;
else
    sort_flag = temp(find(temp),1);   %first non-zero result
end

sort_flag of -1 means that row idx1 is "before" row idx2. sort_flag of 0 means that they are the same for sorting purposes. sort_flag if +1 means that row idx1 is "after" row idx2.

sort_direction_hints is a vector of values, one per column. -1 indicates descending sort; 0 indicates column to be ignored for sorting; +1 indicates ascending sort.

The construction of temp takes constant time proportional to the number of columns. The ~any(temp) could potentially take variable time that is at most proportional to the number of columns. The test could be rewritten to be constant time proportional to the number of columns.

The find() takes variable time that is at most proportional to the number of columns (and could be rewritten to constant time proportional to the number of columns.

The overall result is variable but proportional to the number of columns.

Ameer's would become where m is the number of columns.

This is worst case; an actual dedicated implementation could reduce the constants of proportionality .

Answer 2

[Ameer Hamza]

Although the documentation does not mention the complexity of the algorithm. However, since the lower-bound on sorting have the complexity of , and the experimental results also seem to confirm that

n_rows = round(linspace(1000, 1000000, 50));

t = zeros(1, numel(n_rows));
for i=1:numel(n_rows)
    M = rand(n_rows(i), 3);
    t(i) = timeit(@() sortrows(M));
end

%%
x = n_rows;
y = t;

figure;
plot(x, y, '+');
xlabel('Num. Rows');
ylabel('Execution Time');

The dependance on number of columns also seems to be linear

n_rows = 10:10:500;

t = zeros(1, numel(n_rows));
for i=1:numel(n_rows)
    M = rand(10000, n_rows(i));
    t(i) = timeit(@() sortrows(M));
end

%%
x = n_rows;
y = t;

figure;
plot(x, y, '+');
xlabel('Num. Columns');
ylabel('Execution Time');

So now it depends on your application, whether this complexity is acceptable. However, its performance already seems to be optimal, and you cannot gain much speed by using some other algorithm.