8.3 Initializing Minimum Degree Vertex Tracking
The following data structure is proposed to support efficient tracking the minimum degree vertex during sequential vertex elimination:
A mapping between each vertex in and its degree.
A list which orders by ascending degree.
The procedure compute_degree creates the vertex degree mapping based on and . Algorithm 13 is a candidate for compute_degree.
The procedure merge_sort sorts the list based on the mapping . Its name suggests that a merge sort may be the appropriate sorting algorithm. The minimum number of comparisons required to sort a set of keys is . The merge sort algorithm is in both its best and worst case and is particularly suited for use with linked lists. Furthermore, merge sort does not suffer from the potentially catastrophic worst case stack growth that is common in recursive sorting algorithms. The depth of recursion of a merge sort is bounded by . This implies that sorting 1,000,000 items would require no more than 20 nested function calls. An efficient implementation of merge sort needs at most 4 to 8 bytes of local stack space for each level of recursion.