Hi! What could be the best algorithm for "Merge Sort" where the memory must be used "most effectively"? I just know the standard way to do this, but that's not the most effective way how to use the memory.
This is the only variant which I know:

#include <iostream>
using namespace std;
int main() {
    int arr1[20]= {0,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int arr2[14]= {0,23,25,27,29,31,33,35,37,39,40,41,42,43};
    int arr3[34];
    int indexA=0, indexB=0, indexC=0;

    while((indexA<20) && (indexB<14)) {
        if(arr1[indexA] < arr2[indexB]) {
            arr3[indexC] = arr1[indexA];
            indexA++;
        }
        else {
            arr3[indexC] = arr2[indexB];
            indexB++;
        }
        indexC++;
    }
while(indexA<20) {
    arr3[indexC] = arr1[indexA];
    indexA++;
    indexC++;
}

while(indexB<14) {
    arr3[indexC] = arr2[indexB];
    indexB++;
    indexC++;
}

for (int i=0; i<34; i++)
	cout << arr3[i] << " ";
return 0;
}

Can anyone please advise me a better algorithm for "Merge Sort" which uses the memory in "more effective" way? It can also not be with arrays.

Thank You very much!

Recommended Answers

All 3 Replies

Hi! What could be the best algorithm for "Merge Sort" where the memory must be used "most effectively"? I just know the standard way to do this, but that's not the most effective way how to use the memory.
This is the only variant which I know:

#include <iostream>
using namespace std;
int main() {
    int arr1[20]= {0,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
    int arr2[14]= {0,23,25,27,29,31,33,35,37,39,40,41,42,43};
    int arr3[34];
    int indexA=0, indexB=0, indexC=0;

    while((indexA<20) && (indexB<14)) {
        if(arr1[indexA] < arr2[indexB]) {
            arr3[indexC] = arr1[indexA];
            indexA++;
        }
        else {
            arr3[indexC] = arr2[indexB];
            indexB++;
        }
        indexC++;
    }
while(indexA<20) {
    arr3[indexC] = arr1[indexA];
    indexA++;
    indexC++;
}

while(indexB<14) {
    arr3[indexC] = arr2[indexB];
    indexB++;
    indexC++;
}

for (int i=0; i<34; i++)
	cout << arr3[i] << " ";
return 0;
}

Can anyone please advise me a better algorithm for "Merge Sort" which uses the memory in "more effective" way? It can also not be with arrays.

Thank You very much!

I am familiar with a linked list.
First, I need 2 linked lists and then combine them into the third linked list?
Because, how much I know, "merge sort" just stick together 2 already sorted data structures into the 3rd one and then sort that 3rd data structure. Or am I wrong?

How do you think - how could I use linked lists here?

Thanks!

Your algorithm isn't really mergesort, its just merge. It merges two sorted data. Check wiki for a mergesort implementation.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.