Having issues which Mergesort's compare and ordering part (c++)

merge sort pseudocode
insertion sort
merge sort algorithm with example
merge sort example
quick sort
merge sort python
merge sort java
merge sort c++

I have read and understood how Mergesort works (as a text) and now I'm trying to code it. I have finished the part where you divide the data (I use vectors) until it has each size of 1. Now I have written code for another required part in Mergesort, I don't know how to call it but I just call it "compare and ordering part".

You have 2 vectors and this part is supposed to compare the very first elements, take the smaller element, then remove the chosen element and put it inside a new vector. Doing that untill both vectors have size 0.

I'm sorry for the long code but I really don't see why the very last element is ignored by the code? : / I have added some comments so maybe it is easier to follow what I tried to do.

I tried as input:

vector<int> v1 = {1,4,5,9};
vector<int> v2 = {2,3,6,7,8};

Output:

1 2 3 4 5 6 7 8 0
vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (left.size() > 0 && right.size() > 0) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i) = left.at(0);      // putting the smaller element into the new vector
            left.erase(left.begin());       // removing this smaller element from the (old) vector
        }
        else if (right.at(0) <= left.at(0)) {
            sorted.at(i) = right.at(0);     // see comment above
            right.erase(right.begin());     // see comment above
        }
        else if (left.size() <= 0 && right.size() > 0) {    // if left vector has no elements, then take all elements of the right vector and put them into the new vector
            while (right.size() > 0) {
                sorted.at(i) = right.at(0);
                right.erase(right.begin());
            }
        }
        else if (right.size() <= 0 && left.size() > 0) {    // the same just for the right vector
            while (left.size() > 0) {
                sorted.at(i) = left.at(0);
                left.erase(left.begin());
            }
        }
        i++;
    }
    return sorted;
}

The check of whether one of the arrays has exhausted and other array has remaining elements should be outside the main while loop. So, try to put the below two checks outside.

else if (left.size() <= 0 && right.size() > 0)    

else if (right.size() <= 0 && left.size() > 0)

Think of what will happen when one array has (1) and other (2,3), On adding 1 to the sorted vector, the while(left.size() > 0 && right.size() > 0) condition is false and the loop breaks. So the other elements are ignored.

6.11. The Merge Sort — Problem Solving with Algorithms and Data , Overview of merge sort The full problem is to sort an entire array. It's the combine step, where you have to merge two sorted subarrays, where the real work� I am having an issue with my merge sort visualizer. My program has no issues visualizing bubble sort or quick sort, as I can do the swapping operation of css property values in-place, but I am having

don't know how to call [the] "compare and ordering part"

Conventionally: merge

sorry for the long code

use a

first = *left <= *right ? left : right

and manipulate that, avoiding code replication.

don't see why the very last element is ignored by the code?

left.at(0) <= right.at(0)

and

right.at(0) <= left.at(0)

cover all possible comparison results (equality twice): no further else will get evaluated. Moving "the move parts" to follow "the proper merge" as suggested by Msk, note that the preliminary checks are dispensable - just use "the move loops".


There is a lot to say about your code (starting with commentation) - see code reviews of C++ merge implementations for ideas. If you want code you are in control of reviewed at CR@SE, be sure to be on topic and write a Good Question.

Merge sort algorithm overview (article), Merge sort accesses data sequentially and the need of random access is low. Inversion Count Duration: 1:39 Posted: Mar 15, 2013 Prerequisite – Merge Sort Merge sort involves recursively splitting the array into 2 parts, sorting and finally merging them. A variant of merge sort is called 3-way merge sort where instead of splitting the array into 2 parts we split it into 3 parts.

The code could be simplified:

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    while (1) {
        if (left.at(0) <= right.at(0)) {
            sorted.at(i++) = left.at(0);
            left.erase(left.begin());
            if(left.size == 0){
                do{
                    sorted.at(i++) = right.at(0);
                    right.erase(right.begin());
                }while(right.size != 0);
                return;
            }
        } else {
            sorted.at(i++) = right.at(0);
            right.erase(right.begin());
            if(right.size == 0){
                do{
                    sorted.at(i++) = left.at(0);
                    left.erase(left.begin());
                }while(left.size != 0);
                return;
            }
        }
    }
    return sorted;
}

rather than erasing elements of vectors, indexing could be used instead:

vector<int> sortit(vector<int> &left, vector<int> &right) {
    vector<int> sorted(left.size() + right.size());
    int i = 0;
    int ll = 0;
    int rr = 0;
    while (1) {
        if (left[ll] <= right[rr]) {
            sorted[i++] = left[ll++];
            if(ll == left.size){
                do{
                    sorted[i++] = right[rr++];
                }while(rr != right.size);
                break;
            }
        } else {
            sorted[i++] = right[rr++];
            if(rr == right.size){
                do{
                    sorted[i++] = left[ll++];
                }while(ll != left.size);
                break;
            }
        }
    }
    return sorted;
}

Merge sort, Merging is the process of taking two smaller sorted lists and combining them together into a single, sorted, new list. Figure 10 shows our familiar example list as� Call mergeSort for second half: Call mergeSort(arr, m+1, r) 4. Merge the two halves sorted in step 2 and 3: Call merge(arr, l, m, r) The following diagram from wikipedia shows the complete merge sort process for an example array {38, 27, 43, 3, 9, 82, 10}.

Merge Sort, Now I have written code for another required part in Mergesort, I don't know how to call it but I just call it "compare and ordering part". You have� Merge Sort is a kind of Divide and Conquer algorithm in computer programming. In this tutorial, you will understand the working of merge sort with working code in C, C++, Java, and Python.

The Merge Sort — Problem Solving with Algorithms and Data , Trace the complete execution of the merge sort algorithm when called on the array below, similarly to the example trave of merge sort shown in the lecture slides� Merge sort is a “divide and conquer” algorithm wherein we first divide the problem into subproblems. When the solutions for the subproblems are ready, we combine them together to get the final solution to the problem.

Having issues which Mergesort's compare and ordering part (c++) , Problem : In the course of a merge sort on a 64 element list, how many times must the list be split? 6 times, or log2(64). Problem : Consider the following pairs of� MergeSort is a divide-and-conquer algorithm that splits an array into two halves (sub arrays) and recursively sorts each sub array before merging them back into one giant, sorted array. In this blog, I will provide a simple implementation of MergeSort using C# with comments on every significant line of code for beginners to quickly grasp the

Comments
  • Related: Implementing sorts