Sorted list merging sort
From EverybodyWiki Bios & Wiki
Introduction
| Class | Sorting algorithm |
|---|---|
| Data structure | Array |
| Worst-case performance | |
| Best-case performance | |
| Average performance | , 8.705 for n=1.000 |
| Worst-case space complexity |
How it work? Sorted list merging sort 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 used for multi-thread.
Statistics (average)
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
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;
}
// ------
// 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>
Links
External links
- Script error: The function "in_lang" does not exist. Test of sorting algorithms, generate statics (javascript)
This article "Sorted list merging sort" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Sorted list merging sort. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
