Visual C++ - Sorting Algorithm - Merge Sort Iterative

---

We often using sorting algorithm to sort numbers and strings. Also we have many sorting algorithms. I have explained here on how merge sort algorithm works in iterative mode.

 

The iteration approach requires stacking of the beg(left), end(right) positions that are used in recursion. I have used the vector to store the values and made sure the loop is getting repeated until vector is empty. For DoMerger, we need three arguments - start, mid and right. I have used another vector to store these values and then once all the index positions are calculated, then merely apply the DoMerger on these indexes.

Click here for C++ Bubble Sort Algorithm
Click here for C++ insertion Sort Algorithm
Click here for C++ Merge Sort Recursive Algorithm
Click here for C++ Merge Sort Iterative Algorithm
Click here for C++ Quick Sort Recursive Algorithm
Click here for C++ Quick Sort Iterative Algorithm

The complete program and test run output are given below:

Source Code

---

 

#include <iostream>

#include <queue>

#include <vector>

 

void DoMerge(int numbers[], int left, int mid, int right)

{

    int temp[25];

    int i, left_end, num_elements, tmp_pos;

 

    left_end = (mid - 1);

    tmp_pos = left;

    num_elements = (right - left + 1);

 

    while ((left <= left_end) && (mid <= right))

    {

        if (numbers[left] <= numbers[mid])

            temp[tmp_pos++] = numbers[left++];

        else

            temp[tmp_pos++] = numbers[mid++];

    }

 

    while (left <= left_end)

        temp[tmp_pos++] = numbers[left++];

 

    while (mid <= right)

        temp[tmp_pos++] = numbers[mid++];

 

    for (i=0; i < num_elements; i++)

        numbers[right--] = temp[right];

}

 

void Merge_Sort_Recursive(int numbers[], int left, int right)

{

  int mid;

 

  if (right > left)

  {

    mid = (right + left) / 2;

    Merge_Sort_Recursive(numbers, left, mid);

    Merge_Sort_Recursive(numbers, (mid+1), right);

 

    DoMerge(numbers, left, (mid+1), right);

  }

}

 

struct MergePosInfo

{

    int left;

    int mid;

    int right;

};

 

void Merge_Sort_Iterative(int numbers[], int left, int right)

{

    int mid;

    if (right <= left)

        return;

 

    std::vector<std::pair<int, int> > list;

    std::vector<MergePosInfo> mlist;

    list.push_back(std::pair<int, int>(left, right));

 

    MergePosInfo info;

    while(1)

    {

        if(list.size() == 0)

            break;

 

        left = list.back().first;

        right = list.back().second;

        list.pop_back();

        mid = (right + left) / 2;

 

        if(left < right)

        {

            info.left = left;

            info.right = right;

            info.mid = mid + 1;

 

            mlist.push_back(info);

            list.push_back(std::pair<int, int>(left, mid));

            list.push_back(std::pair<int, int>((mid+1), right));

        }

    }

 

    for(int i = mlist.size() - 1; i >= 0; i--)

    {

        DoMerge(numbers, mlist[i].left, mlist[i].mid, mlist[i].right);

    }

}

 

void MergeSortHelper(int numbers[], int array_size)

{

    //Merge_Sort_Recursive(numbers, 0, array_size - 1);

    Merge_Sort_Iterative(numbers, 0, array_size - 1);

}

 

 

int _tmain(int argc, _TCHAR* argv[])

{

    int arr[] = { 3, 8, 7, 5, 2, 1, 9, 6, 4 };

    int len = sizeof(arr) / sizeof(arr[0]);

 

    MergeSortHelper(arr, len);

 

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

        std::cout << arr[i] << " ";

 

      return 0;

}

 

Output

---

 

1 2 3 4 5 6 7 8 9

 

---

---