mergesort patch for lua-5.1.4

[Dave Rodgers <trepanx@...>]

Here is a patch that replaces the lua-5.1.4 table.sort() quicksort algorithm
with a mergesort algorithm implementation. The primary motivation for
writing this patch was to produce a stable sort (needed for deterministic
operation across multiple hosts). The speedup came as a bonus.

http://dscontracting.ca/trepan/lua/mergesort_lua-5.1.4.diff


Advantages
----------
1. it's a stable sort
2. it's faster  (see the results)
3. it's safer  (modifying the original table during sorting has no effect)

Disadvantages
-------------
1. it uses more memory  (but cleans up after itself immediately)
2. it drags some lower-level code into ltablib.c
  (not an end-user issue, and could be mitigated with some refactoring)


Here are some results:
 garbage collection enabled:  
http://dscontracting.ca/trepan/lua/speedlog-gc.html
 garbage collection disabled: 
http://dscontracting.ca/trepan/lua/speedlog-nogc.html

The 'custom' comparison function was as follows:
 local t = {} -- filled with data
 local comps = 0
 local function comp(a, b)
   local x = t[1]
   comps = comps + 1  
   return a < b
 end

Note that the performance is dominated by whether or not a custom function
is being used (for both algorithms). I guess that all those lua_call()'s 
add up...

-----------------------------------------------------------------------------------------------

Lua WIPS
 luaok (patch/ISO-C)
   Ordered keys, including the addition:
     prev(t [, key]) & rpairs(t) -- reverse iteration
     table.sortkeys(t [, function])
     table.insertkey(t, oldkey, newkey [, value])
     table.usearray(t [,boolean]) -> boolean | t  -- for `all hash' keying
 xnum (package/C99)
   Userdata types for i8, u8, i16, u16, i32, u32, i64, u64, f32, f64.
   Include bitwise operations, and querying to number of the host's C types
   (ex: size_t, ptrdiff_t, time_t, etc...)
 pool (package/C99)
   Memory access with sub-classing, see:
     http://dscontracting.ca/trepan/lua/pool.html
   Sub-classing is made possible by using the userdata `env' for pool 
typing.
   Included sub-class examples are matrix4x4 and mmap.
 luagl3 (package/C99)
   Complete OpenGL 3.2 wrapper with RAII for GL objects.
   No limitations on GLenum values.
   All calls can be intercepted using per-call or global C-side 
#define'd hooks.
 luasfml (package/C99)
   Complete wrapper for sfml-window
   Partial wrapper for sfml-image  (with the additional 
image:FlipY(image) function)

* Ironically, all WIPs are almost complete except for xnum.