| 1971 | // Simon Tatham's linked list merge sort algorithm |
| 1972 | // http://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.html |
| 1973 | function sortLinked(list) { |
| 1974 | var i, |
| 1975 | p, |
| 1976 | q, |
| 1977 | e, |
| 1978 | tail, |
| 1979 | numMerges, |
| 1980 | pSize, |
| 1981 | qSize, |
| 1982 | inSize = 1; |
| 1983 | |
| 1984 | do { |
| 1985 | p = list; |
| 1986 | list = null; |
| 1987 | tail = null; |
| 1988 | numMerges = 0; |
| 1989 | |
| 1990 | while (p) { |
| 1991 | numMerges++; |
| 1992 | q = p; |
| 1993 | pSize = 0; |
| 1994 | for (i = 0; i < inSize; i++) { |
| 1995 | pSize++; |
| 1996 | q = q.nextZ; |
| 1997 | if (!q) break; |
| 1998 | } |
| 1999 | |
| 2000 | qSize = inSize; |
| 2001 | |
| 2002 | while (pSize > 0 || qSize > 0 && q) { |
| 2003 | |
| 2004 | if (pSize === 0) { |
| 2005 | e = q; |
| 2006 | q = q.nextZ; |
| 2007 | qSize--; |
| 2008 | } else if (qSize === 0 || !q) { |
| 2009 | e = p; |
| 2010 | p = p.nextZ; |
| 2011 | pSize--; |
| 2012 | } else if (p.z <= q.z) { |
| 2013 | e = p; |
| 2014 | p = p.nextZ; |
| 2015 | pSize--; |
| 2016 | } else { |
| 2017 | e = q; |
| 2018 | q = q.nextZ; |
| 2019 | qSize--; |
| 2020 | } |
| 2021 | |
| 2022 | if (tail) tail.nextZ = e;else list = e; |
| 2023 | |
| 2024 | e.prevZ = tail; |
| 2025 | tail = e; |
| 2026 | } |
| 2027 | |
| 2028 | p = q; |
| 2029 | } |
| 2030 | |