Data Structures and Algorithms/SortedListMergingSort

Description

Category	Sorting algorithm
Sub category	Merge sort
Name	SortedListMergingSort
Data structure	Array
Comparations	$O(n\log n)$
Timing	$O(n\log n)$
Spacing	$2*n(+n)$ (input + output (+ index table))
Stability	Stable algorithm

How it work? SortedListMergingSort merge sorted list. First, you must detect sorted sub-arrays (by compare values on positions 0-1, 1-2, 2-3...). Or, we can say, always have sorted array size=1. Then merge two arrays (best, arrays with the smallest size) to one. Repeat merging. Trick lies in it, sorted array can compare from top, smaller value move to save, not need more compare with any value in any in this two arrays.

Properties: Algoritm need extra memory (copy from array 1 to array 2 and back). Ist fast. Stable. Can be modified to multi-thread. Version with detect sorted sub-arrays can be modified, return ascendecy (asc), descendency (desc) array as $O(n)$. Can save longer from one of asc or desc sub-arrays.

Note: Merging sorted arrays use TimSort, WikiSort.

Statistics (average)

n         = 1.024
value-min = 0
value-max = n/2     // 50% of array contain some repeating value
------------------
compares  ~ 8.886    (Tim-sort ~8.961)
cycles    ~ 11.273   (Tim-sort ~16.097)
moves     ~ 10.240   (Tim-sort ~13.659, Select-sort ~3.054)

stability = stable

Schematic of work

3 1 2 2 0 3 1 0          // input (array_1)

3-1   2-2   0-3   1-0    // compare top of sorted list A (list array-size = 1) with top of sorted list B (list length 1), C-D, E-F, G-H
1 3   2 2   0 3   0 1    // saved output at end in array_2, cmp = 4 (you still copy from array 1 to array 2 and back, need two array or two array with indexes)

1 3 | 2 2 | 0 3 | 0 1    // input (array_2; A-B, C-D, E-F, G-H is now new sorted array with array-size = 2)
1-----2                  // compare first from AB with first from CD, smaller save
1                        // save
  3---2                  // compare next from AB with first from CD, smaller save
      2                  // save
  3-----2                // compare from last AB with last from CD, smaller save
        2                // save
  3                      // save (copy)
1 2 2 3                  // saved output at end (in array_1), cmp + 3

            0-----0      // compare first (EF) with first (GH)
            0            // save
              3---0      // compare next (EF) with first (GH)
                  0      // save
              3-----1    // compare last (EF) with last (GH)
                    1    // save
              3          // save (copy)
            0 0 1 3      // saved output at end (in array_1), cmp + 3

1 2 2 3 | 0 0 1 3        // new sorted lists
1---------0              // compare first (ABCD) with first (EFGH)
          0              // save
1-----------0            // compare first (ABCD) with second (EFGH)
            0            // save
1-------------1          // compare first (ABCD) with third (EFGH)
1                        // save
  2------------1         // compare second (ABCD) with third (EFGH)
               1         // save
  2--------------3       // compare second (ABCD) with last (EFGH)
  2                      // save
    2------------3       // compare third (ABCD) with last (EFGH)
    2                    // save
      3----------3       // compare last (ABCD) with last (EFGH)
      3                  // save
                 3       // save (copy), cmp + 7
==================
0 0 1 1 2 2 3 3          // output in array_2, return handle to array, suma(cmp) = 4+3+3+7 = 17

Code (javascript)

<div></div>
<script>
// Created by Peter Mlich (2013)
// note: code use too Honzik (? Jaroslav) from VUT Brno, but, i create code before seen his document

// merging part
function listMerging_bounds_part(cmp, i_start, i_end, j_end, m, n)
	{
var cycles = 0;
	var i,j,k;
	i = i_start;
	j = i_end;	// i_end = j_start
	k = i_start;	// k_start = i_start
	while (i<i_end && j<j_end)
		{
cycles++;
		if (cmp(arr[m][i],arr[m][j])>0)
			{arr[n][k] = arr[m][j]; j++; k++;}
		else	{arr[n][k] = arr[m][i]; i++; k++;}
		}
	while (i<i_end)
		{
cycles++;
		arr[n][k] = arr[m][i]; i++; k++;
		}
	while (j<j_end)
		{
cycles++;
		arr[n][k] = arr[m][j]; j++; k++;
		}
glob.cycles += cycles;
glob.moves  += cycles;
	return n;
	}

// Merge sorted list, first sorted lists have length 1 (or can detect sorted, compare(a,b), b-c, c-d...)
function sortedListMergingTop(cmp, start, end, n)
	{
	if (o.size<2) {return o.n;}
	var step, stepmax, tmp, a,b,c, m, n;
	stepmax = ((o.size + 1) >> 1) << 1;
	m = o.n;
	n = o.n==1 ? 2 : 1;
	for (step=1; step<stepmax; step<<=1)	//bounds 1-1, 2-2, 4-4, 8-8...
		{
glob.cycles++;
		a = o.start;
		while (a<o.end)
			{
glob.cycles++;
			b = a + step;
			c = a + (step<<1); // c = a + step + step;
			b = b<o.end ? b : o.end;
			c = c<o.end ? c : o.end;
			listMerging_bounds_part(o.fn_cmp, a, b, c, m, n);
			a = c;
			}
		tmp = m; m = n; n = tmp;
		}
	return m;
	}

// ------

// 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);
	};

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 = sortedListMergingTop(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":64,"cycles":83,"cmps":47}
n 16
*/
</script>