algorithm - Is heap sort supposed to be very slow on MATLAB? -

i wrote heap sort function in matlab , works fine, except when length of input greater or equal 1000, can take long time (e.g. length of 1000 takes half second). i'm not sure if it's matlab doesn't run fast on heap sort algorithm or it's code needs improved. code shown below:

function b = heapsort(a)  [~,n] = size(a); b = zeros(1,n); = 1:n     = build_max_heap(a);     b(n+1-i) = a(1);      temp = a(1);     a(1) = a(n+1-i);     a(n+1-i) = temp;      a(n+1-i) = [];     = heapify(a,1); end end 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function = build_max_heap(a) [~,n] = size(a); m = floor(n/2); = m:-1:1     = heapify(a,i); end end 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

function = heapify(a,i) [~,n] = size(a);  left = 2*i; right = 2*i + 1;  if left <= n      if a(left) >= a(i)         large = left;     else         large = i;     end else     return end if right <= n     if a(right) >= a(large)         large = right;     end end  if large ~=     temp = a(large);     a(large) = a(i);     a(i) = temp;     = heapify(a,large); end end 

i'm aware maybe it's code a(n+1-i) = []; may consume lot of time. when changed [] -999 (lower number of input vector), doesn't took more time.

you should use profiler check lines takes time. it's a(n+1-i) = []; that's slowing down function.

resizing arrays in loops very slow, should try avoid it.

a simple test:

• create function takes large vector input, , iteratively removes elements until it's empty.
• create function takes same vector input , iteratively sets each value 0, inf, nan or else.

use timeit check function faster. you'll see last function approximately 100 times faster (depending on size of vector of course).

the reason why -999 takes more time because a no longer gets smaller , smaller, a = heapify(a,1); won't faster , faster. haven't tested it, if try following in first function you'll faster program (you must insert n+1-i) other places in code well, i'll leave you):

a(n+1-ii) = nan; a(1:n+1-ii) = heapify(a(1:n+1-ii),1); 

note changed i ii. that's partially because want give advice, , partially avoid being reminded not use i , j variables in matlab.