Wrong output for strand sort algorithm

This sorting code depends on strand sort algorithm but when I enter input for example v1=[5,9,13,24,1,6] wrong output given(ans=5;9;13;24;5;9;13;24;1;6). Furthermore, matlab do not give any error but warning which indicates preallocating. How can I amend this code?

function result=myystrandsort(lst)
if length(lst)<=1
    result=lst;
    return;
end
result=[];
sorted=[];
while ~isempty(lst)
    sorted(end+1)=lst(1);
    lst(1)=[];
    it=1;
    while it<=length(lst)
        if sorted(end)<=lst(it)
            sorted(end+1)=lst(it);
            lst(it)=[];
        else
            it=it+1;
        end
    end
    result=[result,sorted];
end
result=result(:);

Answer 1

[Aman]

Hi Mustafa,

There are a few corrections to be made in your code:

• You are not clearing the sorted array after the inner while loop, which is causing the elements to reappear in the result. To fix this, you can define the sorted array inside the while loop like this:

while ~isempty(lst) 
    sorted=[]; 
    sorted(1)=lst(1); 
    lst(1)=[]; 
    it=1; 

• Additionally, you cannot merge result and sorted arrays directly, since both arrays are sorted, you need to merge them in a sorted manner.

Hope this helps!

Answer 2

[Harsh Saxena]

Hi Mustafa,

There are mainly two problems with the code:

1. Sorted list needs to be empty after every iteration of while ~isempty loop.
2. You need to merge the list in sorted order.

function result=myystrandsort(lst)
    if length(lst)<=1
        result=lst;
        return;
    end
    result=[];
    while ~isempty(lst)
        sorted = [];
        sorted(end+1)=lst(1);
        lst(1)=[];
        it=1;
        while it<=length(lst)
            if(sorted(end)<=lst(it))
                sorted(end+1)=lst(it);
                lst(it)=[];
            else
                it=it+1;
            end
        end
        result=merge_sorted(result,sorted);
    end
    result=result(:);
end

Here the merge_sorted function can be created as follows:

function outArray = merge_sorted(in1,in2)
  inAll = [in1(:); flipud(in2(:))]; 
  N = numel(inAll);  
  
  iFront = 1;           
  iBack = N;          
  outArray = zeros(N,1);  
  
  for iOut = 1:N                  
    if inAll(iFront) <= inAll(iBack)   
      outArray(iOut) = inAll(iFront); 
      iFront = iFront+1;              
    else                               
      outArray(iOut) = inAll(iBack);   
      iBack = iBack-1;                
    end
  end
  
end

Hope this helps!

[mustafa]

You saved my life mate.I am appreciate for your help, I can not thank you enough.