Total members 11889 |It is currently Sun Apr 14, 2024 9:56 pm Login / Join Codemiles

Java

C/C++

PHP

C#

HTML

CSS

ASP

Javascript

JQuery

AJAX

XSD

Python

Matlab

R Scripts

Weka





In merge sort we merge two arrays which are already sorted into a larger sorted one. Following code present merge sort example using C++, we describe each section of the code below the code snippet.
Code:
#include <iostream>
using namespace std;
void MergeSort(int* arrayPointer, int firstArrayLimit, int secondArrayLimit);
int main() {
     

    int numbersArray
[] = {23, 6, 4, 15, 664, 22, 18,50,2};
    int arraySize = 9;
    // Printing the array
    cout<<" The Array Before Sorting:"<<endl;
    for (int i = 0; i < arraySize; i++){
        cout << numbersArray[i] << "  ";
    }
    cout << endl;
    // Merging Sort
    for (int i = 1; i < arraySize; i *= 2) {

        for (int j = 0; j < arraySize - i; j += 2*i) {
            int subArrayToBeSortedSize = (2*< arraySize - j) ? 2*: arraySize - j;
            MergeSort(&(numbersArray[j]), i, subArrayToBeSortedSize);
        }
    }

    // Output sorted array
    cout<<" The Array Sorted:"<<endl;
    for (int i = 0; i < arraySize; i++){
        cout << numbersArray[i] << "  ";
    }
    cout << endl;

    return 0;
}

void MergeSort(int* arrayPointer, int firstArrayLimit, int secondArrayLimit) {
    int i = 0;
    int j = firstArrayLimit;
    int k = 0;
    int* tempArray = new int[secondArrayLimit];
    // Take each next smallest element
    while (< firstArrayLimit && j < secondArrayLimit) {
        if (arrayPointer[i] < arrayPointer[j]) {
            tempArray[k] = arrayPointer[i];
            ++i;
        } else {
            tempArray[k] = arrayPointer[j];
            ++j;
        }
        ++k;
    }
    // Copy any remaining elements of the 1st array
    while (< firstArrayLimit) {
        tempArray[k] = arrayPointer[i];
        ++i;
        ++k;
    }
    // Copy any remaining elements of the 2nd array
    while (< secondArrayLimit) {
        tempArray[k] = arrayPointer[j];
        ++j;
        ++k;
    }
    // Copy the merged array back to the original
    for (int iIndex = 0; iIndex < secondArrayLimit; ++iIndex) {
        arrayPointer[iIndex] = tempArray[iIndex];
    }
    delete [] tempArray;
}
 


We now look at the important parts that may need hints to be cleared,

To understand the following loop you have first to notice that the input in this example is just a non sorted single array, to deal with such situation every single array element will be considered an array to be merged with the another one , after that every sorted 2 elements array will be merged with another one and so on , that is why (i) step is i*=2. So, for more illustration:
Iteration#1: Merge (1 element sub_array with 1 element sub_array) repeats to all one elements sub_arrays in main array.
Iteration#2: Merge (2 elements sub_array with 2 element sub_array which are already merged and sorted in Iteration#1) repeat to all 2 elements sub_arrays possible in main array.
Iteration#3: Merge (4 elements sub_array with 4 element sub_array which are already merged and sorted in Iteration#1) repeat to all 2 elements sub_arrays possible in main array.

Code:

    for 
(int i = 1; i < arraySize; i *= 2) {

        for (int j = 0; j < arraySize - i; j += 2*i) {
            int subArrayToBeSortedSize = (2*< arraySize - j) ? 2*: arraySize - j;
            MergeSort(&(numbersArray[j]), i, subArrayToBeSortedSize);
        }
    }
 


Following loop is the main and core of the merging sort, where you decide the sub_array which you will select from the next number in the sorted output sequence.
Code:

    while 
(< firstArrayLimit && j < secondArrayLimit) {
        if (arrayPointer[i] < arrayPointer[j]) {
            tempArray[k] = arrayPointer[i];
            ++i;
        } else {
            tempArray[k] = arrayPointer[j];
            ++j;
        }
        ++k;
    }
 




_________________
M. S. Rakha, Ph.D.
Queen's University
Canada


Author:
Mastermind
User avatar Posts: 2715
Have thanks: 74 time
Post new topic Reply to topic  [ 1 post ] 

  Related Posts  to : merge sort implementation in C++
 Java merge sort example     -  
 bidirectional bubble sort algorithm implementation java     -  
 balloon sort algorithm C++ implementation code-sorting array     -  
 Bubble Sort Algorithm Java Implementation Code-Sorting Array     -  
 lists merge     -  
 How to merge the data into file     -  
 Merge two or more arrays recursively     -  
 multidimensional array merge using PHP     -  
 Implementation of List     -  
 List C++ implementation     -  



Topic Tags

C++ Sorting






Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
All copyrights reserved to codemiles.com 2007-2011
mileX v1.0 designed by codemiles team
Codemiles.com is a participant in the Amazon Services LLC Associates Program, an affiliate advertising program designed to provide a means for sites to earn advertising fees by advertising and linking to Amazon.com