void quick_sort(t_node *left, t_node *right, int start, int end)
{
t_deque deque;
int l;
int r;
int pivot;
if (start >= end)
return ;
// select appropriate pivot to sort effectively.
// In case, I select pivot as deque->top->data!
deque.top = left;
deque.bottom = right;
pivot = left->data;
l = start + 1;
r = end;
// We'll use top->data, so left = left->next
left = left->next;
while (l <= r)
{
while (l <= end && pivot >= left->data)
{
l++;
left = left->next;
}
while (start < r && pivot <= right->data)
{
r--;
right = right->prev;
}
if (l > r)
swap(&deque.top->data, &right->data);
else
swap(&left->data, &right->data);
}
quick_sort(deque.top, right->prev, start, r - 1);
quick_sort(right->next, deque.bottom, r + 1, end);
}