# 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;

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);

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