-
Notifications
You must be signed in to change notification settings - Fork 0
/
mergeSort.cpp
67 lines (59 loc) · 1.59 KB
/
mergeSort.cpp
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
#include <iostream>
#include <cstdlib>
#include <vector>
using namespace std;
void mergeVectors(vector <int>& vectorBeingMerged, int left, int right);
void mergeSort(vector <int>& nonSortedVector, int left, int right)
{
if (left < right)
{
int middle = (left + right) / 2;
mergeSort(nonSortedVector, left, middle);
mergeSort(nonSortedVector, middle + 1, right);
mergeVectors(nonSortedVector, left, right);
}
}
void mergeVectors(vector <int>& vectorBeingMerged, int left, int right)
{
int middlePoint = (left + right) / 2;
vector <int> leftVector;
vector <int> rightVector;
vector <int> mergedVector;
for (int i = left; i <= middlePoint; i++)
{
leftVector.push_back(vectorBeingMerged[i]);
if(middlePoint - left +i +1 <= right)
rightVector.push_back(vectorBeingMerged[middlePoint - left + i+1]);
}
unsigned int leftPointer = 0;
unsigned int rightPointer = 0;
for (int i = 0; i < right - left + 1; i++)
{
if(leftPointer == leftVector.size())
{
mergedVector.push_back(rightVector[rightPointer]);
rightPointer++;
}
else if (rightPointer == rightVector.size())
{
mergedVector.push_back(leftVector[leftPointer]);
leftPointer++;
}
else if (leftVector[leftPointer] <= rightVector[rightPointer])
{
mergedVector.push_back(leftVector[leftPointer]);
leftPointer++;
}
else
{
mergedVector.push_back(rightVector[rightPointer]);
rightPointer++;
}
}
int mergedPointer = 0;
for (int i = left; i <= right; i++)
{
vectorBeingMerged[i] = mergedVector[mergedPointer];
mergedPointer++;
}
}