Mergesort Investigation 17 - worst case data ordering

I’ve benchmarked mergesort variants with randomly-chosen data values, initial data values already sorted, and initial data values sorted in descending order.

What happens to mergesort algorithms when initial data values are chosen for worst case time complexity?

Merge algorithm

Different sort algorithms have different worst case data arrangements. Mergesort does most of its work in the merging of two sorted sub-lists.

If the following code code fragment, p is the head of the left sub-list, and q is the head of the right sub-list. The algorithm won’t work correctly unless p and q are sorted in increasing order.

 1		x := &q
 2		if p.Data < q.Data {
 3			x = &p
 4		}
 5	
 6		h, t := *x, *x
 7		*x = (*x).Next
 8	
 9		for p != nil && q != nil {
10			n := &q
11			if p.Data < q.Data {
12				n = &p
13			}
14			t.Next = *n
15			*n = (*n).Next
16			t = t.Next
17		}
18	
19		t.Next = p
20		if q != nil {
21			t.Next = q
22		}
  • Lines 1-7 set up a head node (h) and a tail node (t) of what will be the merged list. The node with the numerically least data value becomes both. I could simplify this fragment by using Nick Parlante’s dummy head node technique.
  • Lines 9-17 take the node with the numerically smallest data value from either list, and append it to the merged list. The loop continues until one of the lists has zero length.
  • Lines 19-22 put any remaining sub-list fragment on the tail of the merged list.
  • The value of h gets returned.

Lines 19-22 are important. If one or the other sub-list has a lot of low data valued nodes, the loop of lines 9-17 consumes that sub-list first. A number of nodes get left in the other sub-list. We know they’re all higher value than the nodes that got merged, so we can just append the remaining sub-list. No need to compare each node’s data value.

Lines 19-22 are the source of efficiency - we can append the remaining nodes without doing anything more. Sorting a list that started out sorted maximizes this efficiency. Sub-list p has all nodes with data values less than sub-list q. The code only has to check half of the merged list’s data values before appending the entire sub-list q. I saw this in comparison counting pre-sorted and reverse-sorted data of the initial lists.

Worst case time complexity data

Worst case for mergesort is to never have more than 1 node remaining in a sub-list when the algorithm has consumed the other sub-list. In that situation, the efficiency of lines 19-22 never happens.

One way to do this is to arrange the data values of two sub-lists such that the loop of lines 9-17 takes a value from sub-list p on one pass through the loop, then a value from sub-list q on the next pass.

Example code repo explaining this in great detail.

Results

comparisons made vs linked list length

That’s counts of number of comparisons made by the bottom-up algorithm for 4 different arrangements of initial data: randomly chosen, already sorted low-to-high, already sorted high-to-low, and worst case.

Compare to this graph, which shows counts of comparisons made by bottom-up and recursive mergesort algorithms sorting randomly-chosen data values.

The worst case initial data arrangement causes only slight more comparisons to sort than randomly-chosen initial data, never more than 2.7%. I was surprised by this: my intuition was that the worst case data would take a great many more comparisons to sort than randomly chosen data. Upon reflection, the reality makes sense. Randomly-chosen data in longer sorted sub-lists very rarely causes the merge algorithm to leave a large proportion of nodes for the appending in lines 19-23 above. There will certainly be runs of nodes in one sub-list that are numerically lower in value than the head of the other list, but on the whole, the two sub-lists getting merged will both be consumed by the loop, lines 9-17.

No Performance Data

I did not try to benchmark worst case initial data. I created a worst case initial arrangement of data by creating an already sorted list, then recursively creating two sub-lists, each composed by choosing alternating members of the original list. Recursing stops at lists of length 2. The algorithm concatenates the sub-lists, returning a single list. This means that the elements of the linked list, when considered by .Next pointer, will be scattered throughout the address space. Benchmarking sorting where starting lists got re-numbered, but not re-ordered in memory, showed varying results that overshadowed any other effects. I could not figure out a way to have a linked list whose structural elements appeared at higher and higher addresses when accessed via .Next pointers without creating an entire duplicate linked list. This seemed like more trouble than it was worth.