Merge Sort on Doubly Linked List

Question

How do I merge 2 given DLists without having to sort them first? My Sort function doesn't seem to work (it doesn't merge items) when I display on screen

DoublyLinkedList MergeSort(DoublyLinkedList &ls1, DoublyLinkedList &ls2)
{
    DoublyLinkedList ls;
    Initial(ls);
    if(isEmpty(ls1))
        return ls2;
    if(isEmpty(ls2))
        return ls1;
    if(ls1.head->data <= ls2.head->data)
    {
        InsertLast(ls, ls1.head->data);
        RemoveFirst(ls1);
    }
    else
    {
        InsertLast(ls, ls2.head->data);
        RemoveFirst(ls2);
    }
    ls = MergeSort(ls1, ls2);
    return ls;
}

Here my main

int main()
{
    DoublyLinkedList ls1,ls2,ls;
    Initial(ls1);
    Initial(ls2);
    Initial(ls);
    InsertLast(ls1, 9);
    InsertLast(ls1, 5);
    InsertLast(ls1, 1);
    InsertLast(ls1, 4);
    InsertLast(ls1, 3);
    InsertLast(ls2, 12);
    InsertLast(ls2, 6);
    InsertLast(ls2, 2);
    ls=MergeSort(ls1, ls2);
    Print(ls);
    return 0;
}

Outptut: 9 5 1 4 3 12 6 2

Answer 1

After consulting the comments I've fixed the function. Reusing QSort to sort the given lists

DoublyLinkedList MergeSort(DoublyLinkedList &ls1, DoublyLinkedList &ls2)
{
    DoublyLinkedList ls;
    Initial(ls);
    if(isEmpty(ls1))
        return ls2;
    else if(isEmpty(ls2))
        return ls1;
    QuickSort(ls1);
    QuickSort(ls2);
    Node *p = ls1.head;
    Node *q = ls2.head;
    while(p != NULL && q != NULL)
    {
        if(p->data <= q->data)
        {
            InsertLast(ls, p->data);
            p = p->next;
        }
        else
        {
            InsertLast(ls, q->data);
            q = q->next;
        }
    }
    while(p != NULL)
    {
        InsertLast(ls, p->data);
        p = p->next;
    }
    while(q != NULL)
    {
        InsertLast(ls, q->data);
        q = q->next;
    }
    return ls;
}

Here my sub function(InsertLast)

void InsertLast(DoublyLinkedList &ls, int data)
{
    Node *p = CreateNode(data);
    if(p == NULL)
        return;
    if(isEmpty(ls))
    {
        ls.head = ls.tail = p;
    }
    else
    {
        ls.tail->next = p;
        p->prev = ls.tail;
        ls.tail = p;
    }
}