Caută
• oanaunciuleanu

# Merge Sort Algorithm in C++

Merge Sort is a Divide and Conquer Algorithm. It continuously divides in 2 the array, and then each divided part and so on until we have all the values separated, and then starts grouping the values, and sorting them in small groups. This means that the problem is divided into small parts, and those small parts are solved and then merged.

```// Merge Sort

#include <iostream>
using namespace std;

void mergeElements(int arrayOfNumbers[], int left, int middle, int right)
{
int noElemLeftAray = middle - left + 1;
int noElemRightAray =  right - middle;

// Temporary arrays of halves
int leftArray[noElemLeftAray], rightArray[noElemRightAray];

// Copy the values in the 2 new arrays
for (int i = 0; i < noElemLeftAray; i++)
{
leftArray[i] = arrayOfNumbers[left + i];
}

for (int j = 0; j < noElemRightAray; j++)
{
rightArray[j] = arrayOfNumbers[middle + 1 + j];
}

// Merge the arrays back
int indexLeftSubArray = 0;
int indexRightSubArray = 0;
int indexMergedSubarray = left;
while (indexLeftSubArray < noElemLeftAray && indexRightSubArray < noElemRightAray)
{
if (leftArray[indexLeftSubArray] <= rightArray[indexRightSubArray])
{
arrayOfNumbers[indexMergedSubarray] = leftArray[indexLeftSubArray];
indexLeftSubArray++;
}
else
{
arrayOfNumbers[indexMergedSubarray] = rightArray[indexRightSubArray];
indexRightSubArray++;
}
indexMergedSubarray++;
}

// Copy the remaining elements in the left array
while (indexLeftSubArray < noElemLeftAray)
{
arrayOfNumbers[indexMergedSubarray] = leftArray[indexLeftSubArray];
indexLeftSubArray++;
indexMergedSubarray++;
}

// Copy the remaining elements in the right array
while (indexRightSubArray < noElemRightAray)
{
arrayOfNumbers[indexMergedSubarray] = rightArray[indexRightSubArray];
indexRightSubArray++;
indexMergedSubarray++;
}
}

void mergeSort(int arrayOfNumbers[], int left, int right)
{
if (left < right)
{
int middle = left + (right - left) / 2;

// Sort and merge the first and second halves
mergeSort(arrayOfNumbers, left, middle);
mergeSort(arrayOfNumbers, middle + 1, right);

mergeElements(arrayOfNumbers, left, middle, right);
}
}

void printElementsOfArray(int arrayOfNumbers[], int numberOfElements)
{
for (int i = 0; i < numberOfElements; ++i)
{
cout << arrayOfNumbers[i] << " ";
}
cout << endl;
}

int main(void)
{
int arrayOfNumbers[] = {4, 7, 9, 3, 21, 18, 23, 15, 8, 17};
int numberOfElements = sizeof(arrayOfNumbers) / sizeof(arrayOfNumbers[0]);
int startIndex = 0;
int lastIndex = numberOfElements - 1;

mergeSort(arrayOfNumbers, startIndex, lastIndex);
cout<<"The sorted array is: \n";
printElementsOfArray(arrayOfNumbers, numberOfElements);
}```

7 afișare0 comentariu

### Postări recente

Afișează-le pe toate

#### Maximum Length Chain of Pairs in C++

© 2018 by The Art Of Coding. by Oana Unciuleanu

This site was designed with the
.com
website builder. Create your website today.