# Data Structures and Algorithms/InsertionSortMiddle

## Description

 Category Sorting algorithm Insert sort InsertionSortMiddle Array ${\displaystyle O(n\log n)}$ long for log array (base code need to do lot of moves) (original array, input is output) 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>
```