133  * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
143  * pending lists.  This is beautiully simple code, but rather subtle.
151  * 2^k, which is when we have 2^k elements pending in smaller lists,
156  * a third list of size 2^(k+1), so there are never more than two pending.
158  * The number of pending lists of size 2^k is determined by the
167  * 0:  00x: 0 pending of size 2^k;           x pending of sizes < 2^k
168  * 1:  01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
169  * 2: x10x: 0 pending of size 2^k; 2^k     + x pending of sizes < 2^k
170  * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
171  * 4: y00x: 1 pending of size 2^k; 2^k     + x pending of sizes < 2^k
172  * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
181  * When we reach the end of the input, we merge all the pending
192 	struct list_head *list = head->next, *pending = NULL;  in list_sort()  local
193 	size_t count = 0;	/* Count of pending */  in list_sort()
205 	 * - pending is a prev-linked "list of lists" of sorted  in list_sort()
210 	 * - A pair of pending sublists are merged as soon as the number  in list_sort()
211 	 *   of following pending elements equals their size (i.e.  in list_sort()
221 		struct list_head **tail = &pending;  in list_sort()
236 		/* Move one element from input list to pending */  in list_sort()
237 		list->prev = pending;  in list_sort()
238 		pending = list;  in list_sort()
240 		pending->next = NULL;  in list_sort()
244 	/* End of input; merge together all the pending lists. */  in list_sort()
245 	list = pending;  in list_sort()
246 	pending = pending->prev;  in list_sort()
248 		struct list_head *next = pending->prev;  in list_sort()
252 		list = merge(priv, (cmp_func)cmp, pending, list);  in list_sort()
253 		pending = next;  in list_sort()
256 	merge_final(priv, (cmp_func)cmp, head, pending, list);  in list_sort()