Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Merge sort (iterative)
#include <iostream>
#include <vector>
void merge(std::vector<int>& nums, int start, int chunk_size) {
//iterate through first partition (start -> start+chunk_size) while
//iterating through second partition and choose the smallest number
std::vector<int> result;
int mid = start + (chunk_size);
int merge_size = chunk_size*2;
for (int i=start,j=mid; result.size()<merge_size; ) {
if (j>=start+merge_size || (i-start<chunk_size && nums[i]<nums[j]))
result.push_back(nums[i++]);
else
result.push_back(nums[j++]);
}
//copy sorted partitions (result) back to main array (nums)
for (int n=0; n<result.size(); n++) {
nums[start+n] = result[n];
}
}
//iterative merge sort
void merge_sort(std::vector<int>& nums) {
int chunk_size = 1; //start merging one element at a time
for ( ; chunk_size <= nums.size()-1; chunk_size*=2) {
//iterate through this pass merging adjacent chunks
for (int idx=0; idx<nums.size(); idx+=(chunk_size*2)) {
int merge_size = chunk_size*2;
if (nums.size()-idx < merge_size)
merge_size = nums.size()-idx;
if (merge_size==1)
continue;
merge(nums, idx, chunk_size);
}
}
}
template <class T>
void print_v(const std::vector<T>& nums) {
for (int i=0; i<nums.size(); i++) {
std::cout << nums[i] << " ";
}
std::cout << std::endl;
}
int main()
{
std::vector<int> nums { 4,9,6,3,8,5,1,7 };
print_v(nums);
merge_sort(nums);
print_v(nums);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.