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

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