non recursive merge sort

I have to write a non recursive merge sort. I feel like I'm almost there but, It's not sorting the last part of my array. Any help would be awesome. I know the void merge function works because it works with my recursive sort, so it has to be with the iterative function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <iostream>
#include <fstream>
#include <string>
#include <ctime>

void merge(int *a, int size, int low, int high, int mid)
{
	int i, j, k;
	int *c = new int[size];
	i = low;
	k = low;
	j = mid + 1;
	while (i <= mid && j <= high)
	{
		if (a[i] < a[j])
		{
			c[k] = a[i];
			k++;
			i++;
		}
		else
		{
			c[k] = a[j];
			k++;
			j++;
		}
	}
	while (i <= mid)
	{
		c[k] = a[i];
		k++;
		i++;
	}
	while (j <= high)
	{
		c[k] = a[j];
		k++;
		j++;
	}
	for (i = low; i < k; i++)
	{
		a[i] = c[i];
	}
}

void mergeSortIterative(int* arr, int size, int low, int high)
{
	int mid;

	for (int i = 2; i <= size; i *= 2) {
		for (int x = 0; x < size; x += i)
		{
			int newHigh;
			if (x + i - 1 < size - 1)
			{
				newHigh = x + i - 1;
			}
			else
			{
				newHigh = size - 1;
			}
			mid = (newHigh - low) / 2;

			merge(arr, size, x, newHigh, mid);
		}
	}
	return;
}

int main()
{
	std::ifstream inFile;
	std::string inFileName;
	int count = 0;
	int *myIterative;
	int index;
	int nums = 0;

	// Get filename from user
	std::cout << "Enter the input filename: " << std::endl;
	std::cin >> inFileName;

	// Open input file
	inFile.open(inFileName.c_str(), std::ios::app);

	// process input file
	while (!inFile)
	{
		// the file could not be found and opened
		//display error message
		std::cout << "Could not access file" << std::endl;
		std::cin >> inFileName;
	}

	while (inFile >> index) {
		count++;
	}
	myIterative = new int[count];

	inFile.clear();
	inFile.seekg(0, inFile.beg);

	while (inFile >> index) {
		myIterative[nums] = index;
		nums++;
	}


	for (int x = 0; x < nums; x++) {
		std::cout << "Given integers Iterative: " << myIterative[x] << std::endl;
		std::cout << x << std::endl;
	}

	mergeSortIterative(myIterative, nums, 0, nums - 1);
	for (int x = 0; x < nums; x++) {
		std::cout << "Sorted Iterative Array: " << myIterative[x] << std::endl;
		std::cout << x << std::endl;
	}

return 0;
Last edited on
But multiple posts to express a single reply is ok?
Add std::cout << "merge " << low << ' ' << mid << ' ' << high << '\n'; at the beginning of merge() so you can see how it's called. You'll find two problems. First, the mid values aren't right. Second, there is no call for the final merge.
Topic archived. No new replies allowed.