Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Merge Sort — Updated — Most Efficient ways to Implement

Objec­tive : Write Merge Sort algo­rithm to sort ele­ments in an array

Input: A unsorted array, arrA[].

Out­put : A sorted array.

Approach:

Divide and Con­quer: In this approach we divide the main prob­lems into smaller prob­lems, solve them and merge the results to get the final result.

How Divide and con­quer works in Merge Sort:

We divide the ele­ments into two half’s by mid­dle of the array. We solve the left half and right half recur­sively and merge the results.

Merg­ing:

Once the sort­ing is done indi­vid­u­ally on both the half’s, our next task will be merge them. To merge we start with both the arrays at the begin­ning, pick the smaller one put into array and then com­pare the next ele­ments and so on.

Merge Sort

Merge Sort

Time Com­plex­ity : O(nlogn) { O(logn) for divid­ing and O(n) for merging.

Note: we can make merg­ing more effi­cient by imple­ment­ing these approaches

Using Aux­il­iary Array with copy­ing data – In this approach you wont cre­ate new array every­time for merg­ing instead you cre­ate Aux­il­iary array. This will save mem­ory for you.
Alter­nate Merg­ing Between Pri­mary and Aux­il­iary Array: This is the best approach for merg­ing. You don’t copy the entire array to aux­il­iary array for merg­ing instead you do alter­nate merg­ing between main array and aux­il­iary array.

Below is the running time comparison between all three approaches
Data Size Dynamic Memo Allo­ca­tion Algo Using Aux­il­lary Array with copy­ing data Alter­nate Merg­ing Between Pri­mary and Aux­il­lary Array
1 Mil­lion 600–630 mili sec 450–470 mili sec 400–425 mili sec
10 mil­lion 6 secs 4.2 secs 2.3 secs
100 mil­lion 56 secs 46 sec 18 sec


You can find the imple­men­ta­tion of all these approaches here –

GitHub - Three Dif­fer­ent Imple­men­ta­tions of Merge Sorts

Com­plete Code:


Out­put :
1 2 3 4 5 6 9 10

 

You may also like...