This is my favorite sorting algorithm. It’s easy and it also can be parallelized using multiple machines / processes for huuuuge data sets.
Its runtime is (like Quicksort) O(n log(n)). Again here it’s because you split each part into two and work on it recursively.
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 |
include <vector> #include <iostream> #include <string> using namespace std; vector<int> MergeSort(vector<int> input) { if (input.size() == 1) return input; // Split them recursively size_t m = input.size() / 2; // Create two new sub vectors vector<int> leftVector, rightVector; int i = 0; while (i < m) leftVector.push_back(input.at(i++)); while (i < input.size()) rightVector.push_back(input.at(i++)); leftVector = MergeSort(leftVector); rightVector = MergeSort(rightVector); // Now merge the two vectors vector<int> merged; vector<int>::iterator itL = leftVector.begin(); vector<int>::iterator itR = rightVector.begin(); while (itL != leftVector.end() && itR != rightVector.end()) { if (*itL < *itR) { merged.push_back(*itL); ++itL; } else { merged.push_back(*itR); ++itR; } } while (itL != leftVector.end()) { merged.push_back(*itL); ++itL; } while (itR != rightVector.end()) { merged.push_back(*itR); ++itR; } return merged; } |
Most fun is to think about the way Mergesort works in general and find your own implementation. Well, of course each implementation will look pretty much the same in the end…