Merge sort header resulting in random values

GFreak45 (105)
Ok so, I created a simple merge sort header as you can see below.
I am however having some issues with it, the end result in the array is a random assortment of numbers that (most of which) were not in the original array at all, here is the code:

Example Results:

29501 17353 7370 5513 13563

13563 -33686019 -1414812757 -1414812757 0

Press any key to continue . . .

//

30011 22937 8901 23837 17005

17005 -33686019 -1414812757 -1414812757 0

Press any key to continue . . .

//

30011 22937 8901 23837 17005

17005 -33686019 -1414812757 -1414812757 0

Press any key to continue . . .

Sort Header:
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
 
// Sort.h
#ifndef _SORT_H_
#define _SORT_H_

#include <math.h>
#include <vector>

using namespace std;

//NOTE: any _TYPE used must have the operators >=, <=, >, <, ==, and != comparing with their class type
//NOTE 2: _TYPE can not be a pointer

namespace Sort
{
	template<class _TYPE>
	void mergeSort (_TYPE[], unsigned int);
	//mergeSort - sorts the given array via merging them together
	//@param _TYPE[] - the array to sort
	//@param int - the size of the array being sorted

	template<class _TYPE>
	void merge (vector<_TYPE*>&, vector<unsigned int>&, _TYPE*, unsigned int, unsigned int);
	//merge - merges the given _TYPE* (array) with the given index of the array containing the available arrays
	//@param vector<_TYPE*>& - the vector containing all arrays before merging
	//@param vector<unsigned int>& - the vector containing the sizes of all arrays
	//@param _TYPE* - the _TYPE array to be merged with the given index
	//@param unsigned int - the size of the _TYPE* argument
	//@param unsigned int - the index to merge with

	template<class _TYPE>
	void endMerge (vector<_TYPE*>&, vector<unsigned int>&);
	//endMerge - merges all available arrays insied the vector<_TYPE*>& parameter
	//@param vector<_TYPE*>& - the vector containing all arrays to be merged
	//@param vector<unsigned int>& - the size of each array contained in vector<_TYPE*>

	template<class _TYPE>
	void mergeSort (_TYPE values[], unsigned int size)
	{
		vector<_TYPE*> mergers;
		vector<unsigned int> sizes;
		sizes.reserve(static_cast<unsigned int>(log(static_cast<long double>(size))) + 1);
		mergers.reserve(sizes.capacity());
		for (unsigned int x = 0; x < mergers.capacity(); x++)
		{
			int temp = 0;
			mergers.push_back(nullptr);
			sizes.push_back(temp);
		}
		for (unsigned int x = 0; x < size; x += 2)
		{
			unsigned int sortSize = 0;
			if (x + 3 == size) sortSize = 3;
			else if (x + 1 == size) sortSize = 1;
			else sortSize = 2;
			_TYPE* sortArray = new _TYPE [sortSize];
			for (int y = 0; y < 3; y++) *(sortArray + y) = values[x + y];
			for (unsigned int y = 1; y < sortSize; y++)
			{
				for (unsigned int j = y; *(sortArray + j) < *(sortArray + j - 1); j >= 1)
				{
					_TYPE temp = *(sortArray + j);
					*(sortArray + j) = *(sortArray + j - 1);
					*(sortArray + j - 1) = temp;
				}
			}
			if (mergers[0] == nullptr)
			{
				mergers[0] = sortArray;
				sizes[0] = sortSize;
			}
			else merge<_TYPE>(mergers, sizes, sortArray, sortSize, 0);
		}
		endMerge<_TYPE>(mergers, sizes);
		for (unsigned int x = 0; x < size; x++)
			values[x] = *(mergers[0] + x);
		delete[] mergers[0];
	}

	template<class _TYPE>
	void merge (vector<_TYPE*>& mergers, vector<unsigned int>& sizes, _TYPE* sortArray, unsigned int sortSize, unsigned int index)
	{
		unsigned int resultSize = sortSize + sizes[index];
		_TYPE* resultArray = new _TYPE [resultSize];
		unsigned int mergerIndex = 0, sortIndex = 0;
		for (unsigned int x = 0; x < resultSize; x++)
		{
			if (mergerIndex < sizes[index])
			{
				if (sortIndex < sortSize)
				{
					if (*(mergers[index] + mergerIndex) <= *(sortArray + sortIndex))
					{
						*(resultArray + x) = *(mergers[index] + mergerIndex);
						mergerIndex++;
					}
					else
					{
						*(resultArray + x) = *(sortArray + sortIndex);
						sortIndex++;
					}
				}
				else
				{
					*(resultArray + x) = *(mergers[index] + mergerIndex);
					mergerIndex++;
				}
			}
			else
			{
				*(resultArray + x) = *(sortArray + sortIndex);
				sortIndex++;
			}
		}

		if (index + 1 < mergers.size())
		{
			mergers[index] = nullptr;
			if (mergers[index + 1] == nullptr) mergers[index + 1] = resultArray;
			else merge(mergers, sizes, resultArray, resultSize, index + 1);
		}
		else
		{
			mergers[index] = resultArray;
		}
	}

	template<class _TYPE>
	void endMerge (vector<_TYPE*>& mergers, vector<unsigned int>& sizes)
	{
		for (unsigned int x = 0; x < mergers.size(); x++)
		{
			if (mergers[x] != nullptr)
			{
				if (x + 1 < mergers.size())
				{
					if (mergers[x + 1] == nullptr)
					{
						mergers[x + 1] = mergers[x];
						mergers[x] = nullptr;
					}
					else merge(mergers, sizes, mergers[x], sizes[x], x + 1);
				}
				else mergers[0] = mergers[x];
			}
		}
	}
}

#endif


Test Case:
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
 
#include "Sort.h"
#include <iostream>
#include <ctime>

using namespace Sort;
using namespace std;

#define ARR_SIZE 5

int main ()
{
	srand((unsigned)time(NULL));
	srand(rand());
	int arr [ARR_SIZE];
	arr[0] = rand();
	cout << arr[0];
	for (int x = 1; x < ARR_SIZE; x++)
	{
		arr[x] = rand();
		cout << " " << arr[x];
	}

	cout << endl << endl;
	Sort::mergeSort(arr, ARR_SIZE);

	cout << arr[0];
	for (int x = 1; x < ARR_SIZE; x++)
		cout << " " << arr[x];

	cout << endl << endl;
	system("Pause");
	return 0;
}
Ortonas (42)
Oh my goodness, is that you usually sort the numbers?
I am not fallowing, why you are tempting this sort?
Random numbers means that somewhere you are going out of array boundries and accessing random memory slot, duh?
GFreak45 (105)
this is obviously a test i was using for the merge sort header

Random numbers means that somewhere you are going out of array boundries and accessing random memory slot, duh?
I know that but i cant find it... duh?
And iv gone through this call by call but still cant find somewhere that it goes out of array boundaries

and this sort is a merge sort (O(n*(log(n)))) which is MUCH more efficient than bubble sort's (O(n^2)) which is what i assume you use based on your reaction

i was considering creating a heap sort but decided to try out merge since i havent gotten to try a merge sort algorithm before
Last edited on
Topic archived. No new replies allowed.