mergesort.cc

        iterator findMid(iterator& l, iterator& r) const
        {
            iterator slow = l, fast = l;   // slow run 1 step , fast run 2 step per loop.
            while (fast != r)
            {
                if (++fast == r) break;
                ++fast;
                ++slow;
            }
            return slow;
        }
        void mergeSort(iterator& l, iterator& r) const
        {
            if (l == r) return;
            if (l._node == r._node->_prev)  // 2 elements
            {   
                if (*r < *l) swap(*r, *l);
                return;
            }
            iterator m = findMid(l, r); 
            iterator n = m; ++m;
            DListNode<T> *j = n._node->_next, *tail = l._node->_prev, *end = r._node->_next;  // j : the start of second linked list
            mergeSort(l, n);
            j = j->_prev; // Get back to the first array first avoid second array moving
            mergeSort(m, r);
            // do the merge
            j = j->_next; // Go back to the start of the second array
            DListNode<T>* i = tail->_next, *lend = j; // i: the start of the first array
            while (i != lend && j != end)
            {   
                if (i->_data < j->_data) 
                {   
                    tail->_next = i;
                    i->_prev = tail;
                    i = i->_next;
                }
                else
                {   
                    tail->_next = j;
                    j->_prev = tail;
                    j = j->_next;
                }
                tail = tail->_next;
            }
            if (i != lend)
             {  
                tail->_next = i;
                i->_prev = tail;
                while (i->_next != lend) i = i->_next;
                end->_prev = i;
                i->_next = end;
             }
            else
            { 
                tail->_next = j; 
                j->_prev = tail; 
            }
        }