function [sdata] = rfsort(data)

% PURPOSE:  Function 'rfsort' sorts a matrix by each vector in an ascending
% order. If 'data' is a row vector, rfsort sorts the row vector in an 
% ascending order. Recursive Fast Sort is used since it has a time 
% complexity of n*log(n) and deemed as most widely applied sorting algorithm. 
% INPUT:    n by k matrix data 
% OUTPUT:   sortedata: n by k vector of sorted data in an ascending order.
% Programed by Juncai Jiang

[n,k]=size(data);
pivot=zeros(1,k);

if n==1
    sdata=rfsort(data');
    sdata=sdata';
    return;
end

for j=1:1:k
%when the size of the vector decreases to 2, direct comparison is enough.
    if(n==2)
        if(data(1,j)>data(2,j))
            sdata(:,j)=[data(2,j); data(1,j)];
        else sdata(:,j)=data(:,j);
        end
    
    else
       
% It is most efficient to use the median of the vector as the pivot so that 
% we can always devide the vector into two evenly sized subvectors.
% All elements of the first part are less than the pivot, and the elements
% of the other part are greater than or equal to the pivot.
 
pivot(1,j)=median(data(:,j));
leind=find(data(:,j)<pivot(1,j)); % use pointer to index all elements that are smaller than the pivot.
if(isempty(leind)) % This happens when pivot is miniumum of all elements.
    ind=find(data(:,j)>pivot(1,j)); 
    if(isempty(ind));
        sdata(:,j)=data(:,j);
        return;
    end; % This happens when all elements are the same.
        pivot(1,j)=data(ind(1),j); % find a new pilot for the vector.
        leind=find(data(:,j)<pivot(1,j));
end
   
geind=find(data(:,j)>=pivot(1,j)); % use another pointer to index all elements that are smaller than the pivot.
% Recursively sort the two parts of the array and concatenate the sorted
% parts.
sdata(:,j)= [quicksort(data(leind,j));quicksort(data(geind,j))];
end
end