{{subst:AfC submission/draftnew}}<!-- Important, do not remove this line before article has been created. -->

<!-- https://en.wikipedia.org/wiki/Sorting_algorithm -->
<!-- https://en.wikipedia.org/wiki/Sorted_list_merging_sort -->

== Introduction ==

<!-- https://en.wikipedia.org/wiki/Template:Infobox_algorithm -->
{{short description|Sorting algorithm}}
{{No footnotes|date=May 2022}}
{{Infobox Algorithm
| name         = {{PAGENAMEBASE}}
| class        = [[Sorting algorithm]]
| category     = Merge sort
| data         = [[Array data structure|Array]]
| average-time = <math>O(n\log n)</math>, 8.705 for n=1.000
| best-time    = <math>O(n\log n)</math>
| time         = <math>O(n\log n)</math>
| space        = <math>O(2)</math>
| stability    = [[Sorting algorithm#Classification|Stable]]
}}

How it work? {{PAGENAMEBASE}} 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, sorted array have 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 <math>O(n)</math>. Can save longer from one of asc or desc sub-arrays.

== Statistics (average) ==

<pre>
n         = 1.000
value-min = 0
value-max = n/2     // 50% of array contain some repeating value
------------------
compares  ~ 8.705   (Tim-sort ~8.680)
cycles    ~ 11.011  (Tim-sort ~20.969)
moves     ~ 10.000  (Tim-sort ~15.534, Select-sort ~2.979)
stability = stable
</pre>

== Schematic of work ==

<pre style="overflow:auto; width:auto;">
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
</pre>

== Code (javascript) ==

<syntaxhighlight lang="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;
	}

// ------

// code 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>
</syntaxhighlight>

==References==
{{reflist}}

== Links ==

* [https://en.wikipedia.org/wiki/Merge_sort]

=== External links ===
* {{in lang|en}} [https://mlich.zam.slu.cz/js-sort/sorting4-pokus.htm Test of sorting algorithms], generate statics (javascript)
* {{in lang|en}} [https://www.techiedelight.com/merge-given-sorted-linked-lists/]
* [https://aaronice.gitbook.io/lintcode/linked_list/merge_k_sorted_lists/]
* {{in lang|en}} [https://www.datasciencelearner.com/merge-two-sorted-lists-python-methods/]
* {{in lang|en}} [https://dev.to/alisabaj/recursion-and-iteration-what-are-they-and-how-to-use-them-to-merge-sorted-lists-4ofp]


{{sorting}}

[[Category:Sorting algorithms]]
[[Category:Comparison sorts]]