OpenEuphoria

Re: call_func is expensive // Phix much slower

• Posted by Spock Aug 06, 2017
• 1754 views

Well, I had some initial success. I get up to 20% improvement over msort. With some tweaking of constants maybe could extend that to 30%. Here is the algorithm in code. It won't run as is but gives the idea:

 
include bfind.e 
 
function m2sort(seq s) 
 
	-- early out? 
	if ~s < 200 then return insertion_sort(s) end if 
	 
	-- make index 
	seq index = {} 
	for i = 1 to ~s by 20 do 
		index &= { s.i } 
	end for 
	index = m2sort(index) 
 
	-- make the buffer 
	seq store = repeat( {}, ~index ) 
 
	-- store all items in buffer 
	for i = 1 to ~s do 
		obj x = s.i 
		int n = bfind(x, index) 
		store.n &= { x } 
	end for 
 
	-- final sort on all items 
	s = {} 
	for i = 1 to ~store do 
		s &= m2sort( store.i ) 
	end for 
	 
	-- exit 
	return s 
 
	end function 
 

Basically it samples the data and uses that to coarsely place the data into buckets. And then does a final sort of each bucket. BTW, the tilde symbol represents length(). And I have dot notation. For me it's an interesting little side-project. When some more substantial results come through I'll update msort.zip on the contributions page.

Spock