Code covered by the BSD License  

Highlights from
external merge sort

external merge sort

by

 

simulates external merge sort.

extmerge(fno,bufs,pass)
function [out]= extmerge(fno,bufs,pass)
%this function is meant for passes other than 0th pass.
%fno is number of runs created in the last pass.
%bufs is the number of buffers available for this pass.
%pass denotes ,which pass is this.
bufs=bufs;
tmp=[];
br=0;
k=1;
l=int8(fno/bufs);

num=0;
fid=[];
%fcount=0;
while l>=0
            %onum denotes files opened in the last loop.
            %and num will count the files created till this loop.
            onum=num;
            tmp=[];
            for i=1:bufs
                %opening a file
                %fcount=fcount+1;
                %if fcount<=fno
                d=[pass-1,num+1];
                z=int2str(d);
                c=strcat(z,'.txt'); 
                fid(num+1)=fopen(c);
                if fid(num+1)==-1,display('no file left'),break,end
                num=num+1;
                %end
            end
            bufs=num-onum;
            if bufs==0
                %k=k-1;
                break
            end
            display(fid)
           
            %p=1; 
            %initially fill all the buffers by reading one line from files.
            for p=1:bufs 
 
                
                            j=[];
                            j=lin(fid(onum+p));
                
 %           tline = fgetl(fid(onum+p));
            
            
  %          if ~ischar(tline)
   %             p=p+1;
    %            continue;
     %       end
            
            
           
            
            
      %      [h,t]=strtok(tline);
       %     h=str2num(h);
                       
            
        %    j=cat(2,j,h);
            
            %i=1;
         %   while 1
          %      if isempty(t), break, end  
           %     [h,t]=strtok(t);
            %    temp=str2num(h);
                
                
             %   j=cat(2,j,temp);
                
                
                
                         
                
                
             %   i=i+1;
                  
                
            %end
                   
            tmp=[tmp;j];
            %p=p+1;
            end
            
            [m,n]=size(tmp);
            
            %lines=1;
            %while lines<=(bufs+1)*(2.^pass)
            co=[];
            for i=1:n
                co=cat(2,co,1000);
            end

            %try to understand this yourself. 
            conz=1;
            temp=[];
            %for st=1:m*n
             while  conz~=0
                mi=1000;
                for i=1:m
                    
                    a=tmp(i,1);
                    if a<mi
                        mi=a;
                        tu=i;
                    end
                end
                    tmp(tu,1)=1000;
                    tmp=sort(tmp,2);
                    temp=cat(2,temp,mi)  ;
                    tp=(tmp(tu,:)==co);
                    tp=tp(:);
                    
                    for i=1:n
                    if tp(i)~=1
                       cona=1;
                       break; 
                   else
                       cona=0;
                   end
                   end
                    if cona==0
                        x=[];
                        %display('writing output buffer')
                        x=lin(fid(onum+tu));
                        if isempty(x)
                            x=co;
                        end
                            tmp(tu,:)=x;
                        
                        
                    end
                    
                    [ms,ns]=size(temp);
                    if ns==n
                        d=[pass,k];
                        z=int2str(d);
                        c=strcat(z,'.txt');
                        dlmwrite(c, temp, 'delimiter', ' ', 'precision', 6,'-append')  
                        temp=[];
                    end
                
               tp=(tmp==1000);
               tp=tp(:);
               for i=1:m*n
                   if tp(i)~=1
                       conz=1;
                       break; 
                   else
                       conz=0;
                   end
               end
                
             end
             
            
            
            
            
            
            
            
            %if isempty(tmp),break,end           
             %   tmp=algo(tmp);
                
              %  display(tmp)    
                
             %lines=lines+1;   
            %end
            k=k+1
            l=l-1;
end


 


%this out signifies how many runs are created in this pass.
out=k-1
end






Contact us