June 5, 2015 - algorithms cpp

Sorting Algorithm - Merge Sort

Xavier Geerinck

@XavierGeerinck

Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

Merge Sort is a comparison algorithm that tries to sort the dataset by a Divide And Conquer method. The performance of this algorithm is $O(n*log(n))$.

How

We start by splitting the array up into separate elements, then we start by merging pairs together and we make sure that the smallest element is always on the left (this makes sure that our first index on the end is correct too). If the array start getting bigger then 2 elements, then we join those larger arrays by going through their elements one by one and putting the smallest one first.

enter image description here

For the implementation check paragraph §5.4.

Advantages and Disadvantages

Advantages

  • Stable
  • $\Theta(n*lg(n))$ Performance
  • Doesn't need random access to data

Disadvantages

  • Not adaptive
  • $\Theta(n)$ extra space normal
  • $\Theta(lg(n))$ Extra space for LinkedLists

Performance

Worst CaseAverage CaseBest Case
O(n log n)O(n log n)O(n log n)

For the performance of merge sort we will go out from the assumption that $n = 2^k$. This is because we can then split the table in 2 every time.

$T(n) = 2T(n / 2) + cn$

cn stands for the number of operations needed for merging. This is because merging 2 sub tables is $\Theta(n_1 + n_2)$. Now to solve this equation we will just divide both terms by n.

$$\frac{T(n)}{n} = \frac{T(n / 2)}{n / 2} + c$$

And we keep on doing this (recursion) because we need the table to become 1 element big.

$$\frac{T(n/2)}{n/2} = \frac{T(n / 4)}{n / 4} + c$$ $$\frac{T(n/4)}{n/4} = \frac{T(n / 8)}{n / 8} + c$$ $$\frac{T(2)}{2} = \frac{T(1)}{1} + c$$

On the end we just add them both together and we get:

$$\frac{T(n)}{n} = T(1) + ck$$

Because $$T(1)$$ is a constant we can say that $T(n) = O(n*lg(n))$. Also when n is not a power of 2, then we get the same result.

Implementation

Implementing this algorithm is not so hard if you know how to, you need to keep 2 methods in mind:

  • Merge (Combines 2 arrays with each other)
  • MergeSort (Main method, accepts a dataset, splits it and calls this method for those 2 splitted parts)

Then just recursively call MergeSort and you are done.

C++ Code

void merge(vector &v, const vector &left, const vector &right) const {
// We will save our merged array here
vector result;
// Create indexes for the 2 arrays
int idxLeft = 0;
int idxRight = 0;
// Make sure we are not at the end of one of the arrays, else we can't compare
while (idxLeft < left.size() && idxRight < right.size()) {
if (left[idxLeft] < right[idxRight]) {
result.push_back(left[idxLeft]);
idxLeft++;
} else {
result.push_back(right[idxRight]);
idxRight++;
}
}
// Add remaining elements
while (idxLeft < left.size()) {
result.push_back(left[idxLeft]);
idxLeft++;
}
while (idxRight < right.size()) {
result.push_back(right[idxRight]);
idxRight++;
}
// Set our vector on the result
v = result;
};
void merge_sort(vector &v) const {
// Stop running recursively once we have 1 element!
if (v.size() == 1) {
return;
}
// Find the middle element
vector::iterator middle = v.begin() + (v.size() / 2);
// Create our 2 sub arrays
vector left(v.begin(), middle);
vector right(middle, v.end());
// Recursively call MergeSort again, needed for the left and right
merge_sort(left);
merge_sort(right);
// Merge the left and the right array
merge(v, left, right);
}

1.5.5. Benchmark

1001.00010.000100.0001.000.000
Random Elements0.0001630.0016370.0180980.193132.01314
Ascending Elements0.0001450.0014740.0167120.1727181.85952
Descending Elements0.000150.0014720.0168250.1739751.84874

1.5.6. Conclusion

When sorting a Linked List Mergesort is the best choice, however for normal arrays it is better to use other algorithms such as heap sort (which requires less space) or quicksort.

Did you enjoy reading? Or do you want to stay up-to-date of new Articles?

Consider sponsoring me or providing feedback so I can continue creating high-quality articles!

Xavier Geerinck © 2020

Twitter - LinkedIn