Data Structures and Algorithms/InsertionSortMiddle

Description

Category	Sorting algorithm
Sub category	Insert sort
Name	InsertionSortMiddle
Data structure	Array
Comparations	$O(n\log n)$
Timing	long for log array (base code need to do lot of moves)
Spacing	(original array, input is output)
Stability	Stable algorithm

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>