List mergesort

gistfile1.txt

static file_fixup *
FixupListSort(file_fixup *List)
{
    // This is bog-standard mergesort.
    // Base case: 0- and 1-element lists
    if (!List || !List->Next)
    {
        return(List);
    }

    // Split into two halves by having two iterators, one advancing twice as fast
    // as the other.
    file_fixup *SlowIter = List;
    file_fixup *FastIter = List;

    while (FastIter->Next && FastIter->Next->Next)
    {
        SlowIter = SlowIter->Next;
        FastIter = FastIter->Next->Next;
    }

    file_fixup *SecondHalf = SlowIter->Next;
    SlowIter->Next = NULL;

    // Sort both halves recursively
    file_fixup *A = FixupListSort(List);
    file_fixup *B = FixupListSort(SecondHalf);

    // Then merge
    file_fixup *Head = NULL;
    file_fixup **PointerToNext = &Head;

    // As long as there are items in both lists, pick whichever is considered "less"
    while (A && B)
    {
        if (FixupLess(*B, *A))
        {
            *PointerToNext = B;
            PointerToNext = &B->Next;
            B = B->Next;
        }
        else
        {
            *PointerToNext = A;
            PointerToNext = &A->Next;
            A = A->Next;
        }
    }

    // Append the rest of whatever list has left-over elements
    *PointerToNext = A ? A : B;
    return(Head);
}