# Merge Sort Iterative

Merge sort is a Divide and Conquer algorithm. It divides input array in two halves, calls itself for the two halves and then merges the two sorted halves.

```									```public static void MergeSortIterative(ref int[] data)
{
int currentSize;
int leftStart;

for (currentSize = 1; currentSize <= data.Length - 1; currentSize = 2 * currentSize)
{
for (leftStart = 0; leftStart < data.Length - 1; leftStart += 2 * currentSize)
{
int mid = leftStart + currentSize - 1;
int rightEnd = Math.Min(leftStart + 2 * currentSize - 1, data.Length - 1);

Merge(ref data, leftStart, mid, rightEnd);
}
}
}

private static void Merge(ref int[] data, int left, int mid, int right)
{
int i, j, k;
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];

for (i = 0; i < n1; i++)
L[i] = data[left + i];

for (j = 0; j < n2; j++)
R[j] = data[mid + 1 + j];

i = 0;
j = 0;
k = left;

while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
data[k] = L[i];
i++;
}
else
{
data[k] = R[j];
j++;
}

k++;
}

while (i < n1)
{
data[k] = L[i];
i++;
k++;
}

while (j < n2)
{
data[k] = R[j];
j++;
k++;
}
}```
```

### Example

```									```int[] data = new int[] { -1, 25, -58964, 8547, -119, 0, 78596 };
MergeSortIterative(ref data);```
```

### Output

```									```-58964
-119
-1
0
25
8547
78596```
```