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!

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.

This article has been dead for over six months. Start a new discussion instead.