Нерекурсивная сортировка слиянием с двумя вложенными циклами — как?

Это не так сложно. Рассмотрим рекурсивное слияние:

       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
            /     \               split
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
      /   \         /  \          split
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
  / \     / \     / \     / \     split
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

Если вы заметили, когда вы разделяетесь, вы ничего не делаете. Вы просто указываете рекурсивной функции частично отсортировать массив. Сортировка массива состоит из первой сортировки обеих половин, а затем их слияния. Итак, в основном, что у вас есть это:

+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
| | | | | | | | | | | | | | | |
+-+ +-+ +-+ +-+ +-+ +-+ +-+ +-+
  \ /     \ /     \ /     \ /     merge
  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+
            \     /               merge
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+

Теперь отсюда должно быть очевидно. Сначала вы объединяете элементы массива 2 на 2, затем 4 на 4, затем 8 на 8 и т. д. То есть внешнее for дает вам 2, 4, 8, 16, 32,... (именно это вызывает размер сегмента, потому что i цикла содержит это число), а внутренний for (скажем, с итератором j) проходит по массиву, i путем i слияния array[j...j+i/2-1] с array[j+i/2..j+i-1].

Я бы не стал писать код, так как это домашнее задание.

Изменить: изображение того, как работает внутренний for

Представьте, если i равно 4, то есть вы находитесь на этом этапе:

  +-+-+  +-+-+  +-+-+  +-+-+
  | | |  | | |  | | |  | | |
  +-+-+  +-+-+  +-+-+  +-+-+
      \   /         \  /          merge
    +-+-+-+-+     +-+-+-+-+
    | | | | |     | | | | |
    +-+-+-+-+     +-+-+-+-+

у вас будет for, который однажды даст вам 0 (то есть 0*i) как j, а затем 4 (то есть 1*i) как j. (если бы i было 2, у вас было бы j как 0, 2, 4, 6)

Теперь один раз нужно слить array[0..1] с array[2..3] (которое формулируется array[j..j+i/2-1] и array[j+i/2..j+i-1] с j = 0) а затем array[4..5] с array[6..7] (которое формулируется теми же формулами array[j...j+i/2-1] и array[j+i/2..j+i-1] потому что теперь j = 4) То есть:

i = 4:
       +-+-+-+-+-+-+-+-+
       | | | | | | | | |
       +-+-+-+-+-+-+-+-+
        ^ ^ ^ ^ ^ ^ ^ ^
        | | | | | | | |
       / / / /   \ \ \ \
     (j  =  0)   (j  =  4)
      | | | |     | | | |
      j | | |     j | | |
      | | | j+i-1 | | | j+i-1
      | | j+i/2   | | j+i/2
      | j+i/2-1   | j+i/2-1
      | | | |     | | | |
      | | | |     | | | |
      \ / \ /     \ / \ /
       v   v       v   v
       merge       merge

Надеюсь, это хоть немного понятно.

Дополнительная помощь: подсказка, если вы не совсем понимаете, как работает for:

for (statement1; condition; statement2)
{
    // processing
}

это как писать

statement1;
while (condition)
{
    // processing
    statement2;
}

Итак, если вы всегда писали

for (int i = 0; i < 10; ++i)

это означало, начиная с 0, пока i меньше 10, сделать что-то с i, а затем увеличить его. Теперь, если вы хотите, чтобы i менялось по-другому, вы просто меняете statement2, например:

for (int i = 1; i < 1024; i *= 2)

(Попробуйте понять, как работает этот последний for, основываясь на его эквиваленте while, который я вам написал)

Вот моя ленивая, итеративная/восходящая реализация сортировки слиянием, которая использует std::merge:

template<class InIt, class OutIt>
OutIt mergesort(InIt begin, InIt const end, OutIt o /* auxiliary buffer */)
{
    ptrdiff_t j;
    for (j = 0; begin != end; ++begin, ++j)
    {
        for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
        {
            o = std::merge(o - n * 2, o - n, o - n, o, begin - n * 2);
            o = std::swap_ranges(begin - n * 2, begin, o - n * 2);
        }
        *o = *begin;
        ++o;
    }
    --j;
    for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
    {
        if (j & n)
        {
            o = std::merge(o - (m + n), o - m, o - m, o, o - (m + n));
            o = std::swap_ranges(begin - (m + n), begin, o - (m + n));
            m += n;
        }
    }
    return o;
}

Вот версия на месте, в которой используется std::inplace_merge:

template<class InIt>
InIt inplace_mergesort(InIt begin, InIt const end)
{
    ptrdiff_t j;
    for (j = 0; begin != end; ++begin, ++j)
    {
        for (ptrdiff_t n = 1; n <= j && j % (n * 2) == 0; n *= 2)
        { std::inplace_merge(begin - n * 2, begin - n, begin); }
    }
    --j;
    for (ptrdiff_t m = 1, n = 1; n <= j; n *= 2)
    {
        if (j & n)
        {
            std::inplace_merge(begin - (m + n), begin - m, begin);
            m += n;
        }
    }
    return begin;
}

Вот версия C# восходящей сортировки слиянием (более подробную информацию вы можете найти в моем блоге @ http://dream-er.blogspot.com/2014/07/mergesort-arrays-and-lists)..html)

void BottomUpMergesort(int[] a)
        {
            int[] temp = new int[a.Length];
            for (int runWidth = 1; runWidth < a.Length; runWidth = 2 * runWidth)
            {
                for (int eachRunStart = 0; eachRunStart < a.Length; 
                    eachRunStart = eachRunStart + 2 * runWidth)
                {
                    int start = eachRunStart;
                    int mid = eachRunStart + (runWidth - 1);
                    if(mid >= a.Length)
                    {
                        mid = a.Length - 1;
                    }
                    int end = eachRunStart + ((2 * runWidth) - 1);
                    if(end >= a.Length)
                    {
                        end = a.Length - 1;
                    }

                    this.Merge(a, start, mid, end, temp);
                }
                for (int i = 0; i < a.Length; i++)
                {
                    a[i] = temp[i];
                }
            }

И слияние определяется как:

void Merge(int[] a, int start, int mid, int end, int[] temp)
        {
            int i = start, j = mid+1, k = start;
            while((i<=mid) && (j<=end))
            {
                if(a[i] <= a[j])
                {
                    temp[k] = a[i];
                    i++;
                }
                else
                {
                    temp[k] = a[j];
                    j++;
                }
                k++;
            }
            while(i<=mid)
            {
                temp[k] = a[i];
                i++;
                k++;
            }
            while (j <= end)
            {
                temp[k] = a[j];
                j++;
                k++;
            }
            Assert.IsTrue(k == end+1);
            Assert.IsTrue(i == mid+1);
            Assert.IsTrue(j == end+1);
        }

        }

Для справки здесь используется TopDownMergesort:

void TopDownMergesort(int[] a, int[] temp, int start, int end)
        {
            if(start==end)
            {
                //run size of '1'
                return;
            }
            int mid = (start + end) / 2;
            this.TopDownMergesort(a, temp, start, mid);
            this.TopDownMergesort(a, temp, mid + 1, end);
            this.Merge(a, start, mid, end, temp);
            for(int i = start;i<=end;i++)
            {
                a[i] = temp[i];
            }
        }

Модульные тесты

[TestMethod]
        public void BottomUpMergesortTests()
        {
            int[] a = { 13, 4, 1, 3, 8, 11, 9, 10 };
            this.BottomUpMergesort(a);
            int[] b = { 1, 3, 4, 8, 9, 10, 11, 13 };
            Assert.IsTrue(a.Length == b.Length);
            for (int i = 0; i < a.Length; i++)
            {
                Assert.IsTrue(a[i] == b[i]);
            }
            List<int> l = new List<int>();
            for (int i = 10; i >= 1; i--)
            {
                l.Add(i);
            }
            var la = l.ToArray();
            this.BottomUpMergesort(la);
            for (int i = 1; i <= 10; i++)
            {
                Assert.IsTrue(la[i - 1] == i);
            }
            l.Clear();
            for (int i = 16; i >= 1; i--)
            {
                l.Add(i);
            }
            la = l.ToArray();
            this.BottomUpMergesort(la);
            for (int i = 1; i <= l.Count; i++)
            {
                Assert.IsTrue(la[i - 1] == i);
            }
        }

Вот реализация Java

public static <T extends Comparable<? super T>> void iterativeMergeSort(T[] seed) {

    for (int i = 1; i <seed.length; i=i+i)
    {
        for (int j = 0; j < seed.length - i; j = j + i+i)
        {
            inPlaceMerge(seed, j, j + i-1, Math.min(j+i + i -1, seed.length -1));
        }
    }       
}
public static <T extends Comparable<? super T>>  void inPlaceMerge(T[] collection, int low, int mid, int high) {
    int left = low;
    int right = mid + 1;

    if(collection[mid].equals(collection[right])) {
        return ;//Skip the merge if required
    }
    while (left <= mid && right <= high) {          
        // Select from left:  no change, just advance left
        if (collection[left].compareTo(collection[right]) <= 0) {
            left ++;
        } else { // Select from right:  rotate [left..right] and correct
            T tmp = collection[right]; // Will move to [left]
            rotateRight(collection, left, right - left);
            collection[left] = tmp;
            // EVERYTHING has moved up by one
            left ++; right ++; mid ++;
        }
    }       
}

Вот семя закрытого Integer[] модульного теста;

@Before
public void doBeforeEachTestCase() {
    this.seed = new Integer[]{4,2,3,1,5,8,7,6};
}
@Test
public void iterativeMergeSortFirstTest() {
    ArrayUtils.<Integer>iterativeMergeSort(seed);
    Integer[] result = new Integer[]{1,2,3,4,5,6,7,8};
    assertThat(seed, equalTo(result));  
}