Editing Merge sort (section)

===Bottom-up implementation using lists===
[[Pseudocode]] for bottom-up merge sort algorithm which uses a small fixed size array of references to nodes, where <code>array[i]</code> is either a reference to a list of size 2<sup>''i''</sup> or ''[[Null pointer|nil]]''. ''node'' is a reference or pointer to a node. The <code>merge()</code> function would be similar to the one shown in the top-down merge lists example, it merges two already sorted lists, and handles empty lists. In this case, <code>merge()</code> would use ''node'' for its input parameters and return value.

 '''function''' merge_sort(''node'' head) '''is'''
     // return if empty list
     '''if''' head = nil '''then'''
         '''return''' nil
     '''var''' ''node'' array[32]; initially all nil
     '''var''' ''node'' result
     '''var''' ''node'' next
     '''var''' ''int''  i
     result := head
     // merge nodes into array
     '''while''' result ≠ nil '''do'''
         next := result.next;
         result.next := nil
         '''for''' (i = 0; (i < 32) && (array[i] ≠ nil); i += 1) '''do'''
             result := merge(array[i], result)
             array[i] := nil
         // do not go past end of array
         '''if''' i = 32 '''then'''
             i -= 1
         array[i] := result
         result := next
     // merge array into single list
     result := nil
     '''for''' (i = 0; i < 32; i += 1) '''do'''
         result := merge(array[i], result)
     '''return''' result