CareerCup

node* insert(node* ptr,int x)
{
node* ptr1=ptr,ptr2=NULL;
ptr2=(node*)malloc(sizeof(node));
if(ptr!=NULL)
{
while(ptr!=NULL && ptr->data >= x)
{
ptr1=ptr;
ptr=ptr->next;
}
if(ptr!=NULL)
{
ptr->left->right=ptr2;
ptr2->right=ptr;
ptr->left=ptr2;
}
else
{
ptr1->right=ptr2;
ptr2->left=ptr1;
ptr2->right=NULL;
}
}
else
{
ptr2->data=x;
ptr2->left=NULL;
ptr2->right=NULL;
}
}

Pure insertion sort, Like binary search, go to the middle of the selected set everytime and see if the number is greater .. then, once you find the smallest.. traverse from there and insert it...

Deletion is also same !!

-> Obtain a pointer to the begin, middle and end of the double linked list and store it.
-> For every new element to be inserted, 
     check if it is less than middle element or not {O(1)}
     traverse to the left or right based on the comparison {O(n/2)}
-> worst case complexity: O(n/2)
        space complexity: O(1)

node * RecInsertDLL(p, prev, num)
{
if(p == null || p->value > num)
{
x = new node;
x->prev = prev;
x->next = p;
x->value = num;
return x;
}

x->next = RIDLL(p->next, p);
return p;
}