O>Сам алгоритм сортировки обычного численного массива у меня есть, проблема в другом — незнаю как переделать его (алгоритм) так, чтобы он сортировал список.

typedef std::list<int> intlist;
typedef intlist::iterator iter;

void sort(intlist& data, iter begin, iter end)
{
  // [begin,end)
  if(begin == end) return; // 0 элементов
  end--;
  // [begin,end]
  if(begin == end) return; // 1 элемент
  end++;
  // [begin,end)

  // разбить список пополам
  iter m1 = begin, m2 = end;
  while(true)
  {
    if(m1 == m2) break;
    m1++;
    if(m1 == m2) break;
    m2--;
  }
  // m1 == m2

  // отсортировать под-интервалы
  sort(data, begin, m1); // [begin, m)
  sort(data, m1, end); // [m, end)

  // слияние
  while(begin != m1 && m1 != end)
  {
    if(*begin < *m1)
      begin++;
    else
    {
      m2 = m1;
      do { m2++; } while(m2 != end && *m2 < *begin);
      // перенести [m1,m2) перед begin
      data.splice(begin, data, m1, m2);
      m1 = m2;
    }
  }
}

К>>  // разбить список пополам
К>>  iter m1 = begin, m2 = end;
К>>  while(true)
К>>  {
К>>    if(m1 == m2) break;
К>>    m1++;
К>>    if(m1 == m2) break;     ?????????????
К>>    m2--;
К>>  }
К>>  // m1 == m2
К>>

while(m1 < m2)

while(m1 != m2)
{
  m1++; m2--;
}

// sorttest.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

#include <list>
#include <iostream>
using namespace std;

typedef list<int> intlist;
typedef intlist::iterator iter;

void dump(intlist& data, iter i1, iter i2)
{
    iter b = data.begin();
    iter e = data.end();
    
    cout << "{";

    while(true)
    {
        if(b == i1 && b == i2)
            cout << "|";
        else if(b == i1)
            cout << "[";
        else if(b == i2)
            cout << "]";
        else
            cout << " ";

        if(b == e)
            break;

        cout << *b;
        b++;
    }
    cout << "}";
}

void msort(int depth, intlist& data, iter begin, iter end)
{
    // [begin,end)
    if(begin == end) return; // 0 элементов
    end--;
    // [begin,end]
    if(begin == end) return; // 1 элемент
    end++;
    // [begin,end)
    
    cout << depth << " msort. ";
    dump(data, begin, end);
    cout << endl;

    // разбить список пополам
    iter m1 = begin, m2 = end;
    while(true)
    {
        if(m1 == m2) break;
        m1++;
        if(m1 == m2) break;
        m2--;
    }
    // m1 == m2

    cout << depth << " middle ";
    dump(data, m1, m2);
    cout << endl;

    // отсортировать под-списки
    iter m0;    

    m0 = begin; m0--; // запомнить итератор ПЕРЕД сортируемым участком (иначе он уплывет)
    msort(depth+1, data, begin, m1); // [begin, m)
    begin = m0; begin++; // и восстановить

    m0 = m1; m0--; // то же самое
    msort(depth+1, data, m1, end); // [m, end)
    m1 = m0; m1++;

    cout << depth << " merge: ";
    dump(data, begin, end);
    cout << endl;

    // слияние

    m0 = begin; m0--; // для отладочных целей :)

    while(begin != m1 && m1 != end)
    {
        cout << depth << " step   ";
        dump(data, begin, end);

        if(*begin < *m1)
        {
            cout << " skip";
            begin++;
        }
        else
        {
            cout << " splice";

            m2 = m1;
            // найдем фрагмент для перемещения
            do { m2++; } while(m2 != end && *m2 < *begin);
            // переместим его
            data.splice(begin, data, m1, m2);
            // восстановим указатель (m2 остался на месте; begin - после перемещенного фрагмента)
            m1 = m2;
        }

        cout << endl;
    }

    begin = m0; begin++; // восстановим, чтобы красиво распечатать

    cout << depth << " sorted ";
    dump(data, begin, end);
    cout << endl;   
}


int main(int argc, char* argv[])
{
    intlist data;
    int i;
    for(i = 8; i > 0; i--)  data.push_back(i);

    msort(1, data, data.begin(), data.end());

    return 0;
}

1 msort. {[8 7 6 5 4 3 2 1]}
1 middle { 8 7 6 5|4 3 2 1 }
2 msort. {[8 7 6 5]4 3 2 1 }
2 middle { 8 7|6 5 4 3 2 1 }
3 msort. {[8 7]6 5 4 3 2 1 }
3 middle { 8|7 6 5 4 3 2 1 }
3 merge: {[8 7]6 5 4 3 2 1 }
3 step   {[8 7]6 5 4 3 2 1 } splice
3 sorted {[7 8]6 5 4 3 2 1 }
3 msort. { 7 8[6 5]4 3 2 1 }
3 middle { 7 8 6|5 4 3 2 1 }
3 merge: { 7 8[6 5]4 3 2 1 }
3 step   { 7 8[6 5]4 3 2 1 } splice
3 sorted { 7 8[5 6]4 3 2 1 }
2 merge: {[7 8 5 6]4 3 2 1 }
2 step   {[7 8 5 6]4 3 2 1 } splice
2 sorted {[5 6 7 8]4 3 2 1 }
2 msort. { 5 6 7 8[4 3 2 1]}
2 middle { 5 6 7 8 4 3|2 1 }
3 msort. { 5 6 7 8[4 3]2 1 }
3 middle { 5 6 7 8 4|3 2 1 }
3 merge: { 5 6 7 8[4 3]2 1 }
3 step   { 5 6 7 8[4 3]2 1 } splice
3 sorted { 5 6 7 8[3 4]2 1 }
3 msort. { 5 6 7 8 3 4[2 1]}
3 middle { 5 6 7 8 3 4 2|1 }
3 merge: { 5 6 7 8 3 4[2 1]}
3 step   { 5 6 7 8 3 4[2 1]} splice
3 sorted { 5 6 7 8 3 4[1 2]}
2 merge: { 5 6 7 8[3 4 1 2]}
2 step   { 5 6 7 8[3 4 1 2]} splice
2 sorted { 5 6 7 8[1 2 3 4]}
1 merge: {[5 6 7 8 1 2 3 4]}
1 step   {[5 6 7 8 1 2 3 4]} splice
1 sorted {[1 2 3 4 5 6 7 8]}