Data Structures and Algorithms/InsertionSortMiddle

Description

How it work? InsertionSortMiddle work as insert sort. Get next value (i+1) and insert to sorted array. Check possition from middle of sorted array, then middle of part...

Properties: Algoritm not need extra memory. Ist slow for large array (moving a large array takes a lot of time). Have minimal comparation operations of all know algorithms (without counting sorts). Stable.

Statistics from real code execution (average)

n         = 1.024
value-min = 0
value-max = n/2     // 50% of array contain some repeating value
------------------
compares  ~ 8.825    (Tim-sort ~8.961)
cycles    ~ 273.362  (Tim-sort ~16.097)
moves     ~ 263.514  (Tim-sort ~13.659, Select-sort ~3.054)
stability = stable

Schematic of work

3 1 2 2 0 3 1 0    // input

3                  // is first sorted array, (left = 0), half = 0, mid = 0 + floor(half / 2) (first pos_b), ''' cmp = 0 '''
. 1                // next i = 1, value = array[i] = 1, mid = 0
3-1                // compare 3-1
1 3                // 13 is now output, half = i, mid = 0 + floor(half / 2), ''' cmp + 1 ''' 
.
.   2              // next i, array[i], mid = 0
1---2              // compare(array[i], array[mid]), compare>=0, half = floor(half / 2), left = mid, mid = left + half
  3-2              // compare(array[i], array[mid]), compare<0, end (because half = 0, cannot more divide), half = i, mid = 0 + round(half / 2), ''' cmp + 2 ''' 
1 2 3
  .                // ... note: for simplify, i remove lot of repeating text
      2            // next i, mid = 1
  2---2            // compare>=0, mid = left + half
  . 3-2            // compare<0, end, ''' cmp + 2 '''
1 2 2 3
  .
  .     0          // next i, mid = 1
  2-----0          // compare<0, mid = left - half
1-------0          // compare<0, end, ''' cmp + 2 '''
0 1 2 2 3
    .
          3        // next i, mid = 2
    2-----3        // compare>=0, mid = left + half
    . 2---3        // compare>=0, mid = left + half
    .   3-3        // compare>=0, end, ''' cmp + 3 '''
0 1 2 2 3 3
    .
    .       1      // next i, mid = 2
    2-------1      // compare<0, mid = left - half
  1---------1      // compare>=0, end, ''' cmp + 2 ''' (my alg. code here compute cmp+3, because compare zero)
0 1 1 2 2 3 3
      .
              0    // next i, mid = 3
      2-------0    // compare<0, mid = left - half
  1-----------0    // compare<0, mid = left - half
0-------------0    // compare>=0, end, ''' cmp + 3 '''
===============
0 0 1 1 2 2 3 3    // output, suma(cmp) = 1+2+2+2+3+2+3 = 15

Code (javascript)

<div></div>
<script>
// Created by Peter Mlich (2017)

// insert new item into sorted array, check position from middle of array
// note: algorithm code is differend from schema, but simplest
function sortInsertMiddle(cmp, start, end, n)
	{
	if (o.size<2) {return o.n;}
	var i, i_start, i_end, left, right, mid, mid_sub;
	i_start = o.start + 1;
	i_end   = o.end;
	i       = i_start;
	while (i<i_end)
		{
glob.cycles++;
		// find position
		left  = o.start - 1;
		right = i;
		mid_sub = right - left;
		while (true)
			{
glob.cycles++;
			mid = left + (mid_sub>>1);
			if (o.fn_cmp(arr[o.n][i], arr[o.n][mid])>=0)
				{
				left    = mid;
				mid_sub = right - left;
				if (mid_sub<=1) {mid++; break;}
				}
			else	{
				right   = mid;
				mid_sub = right - left;
				if (mid_sub<=1) {break;}
				}
			}
		// move to position, shift array
		arrShift(arr[o.n], mid, i);
		i++;
		}
	return o.n;
	}

// ------

// note: code is not optimalized - draft version from my tester
function sortCompare (a, b)
	{
glob.cmps++;
	var c = a - b;
	return c>0 ? 1 : (c<0 ? -1 : 0);
	};

function arrShift(list, a, b)	// move last (b) on top (a), alternation: splice or copyWithin
	{
	if (b<=a || a<0 || b<0) {return;}
	var tmp = list[b];
glob.cycles += b - a;
glob.moves += b - a;
	while (a<b)
		{
        	list[b] = list[--b];
		}
	list[a] = tmp;
	}

var arr  = [null, [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4], [-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1]]
var glob = {moves: 0, cycles: 0, cmps: 0};
var o    = {start: 0, end: 16, size: 16 - 0, n: 1, moves: 0, cycles: 0, fn_cmp: sortCompare};
var log = [], i=0, n;

log[i++] = 'array-before ' + JSON.stringify(arr[1])

o.n = sortInsertMiddle(o.fn_cmp, o.start, o.end, o.n);

log[i++] = 'array-after ' + JSON.stringify(arr[o.n])
log[i++] = 'glob ' + JSON.stringify(glob)
log[i++] = 'n ' + JSON.stringify(o.end - o.start)
document.getElementsByTagName('DIV')[0].innerHTML = log.join('<br>')

/*
array-before [7,7,4,3,4,7,6,7,0,1,0,6,7,2,2,4]
array-after [0,0,1,2,2,3,4,4,4,6,6,7,7,7,7,7]
glob {"moves":66,"cycles":125,"cmps":44}
n 16
*/
</script>