A stable sorting algorithm is one that preserves the origina

A stable sorting algorithm is one that preserves the original order of equal keys. Mergesort is an unstable sorting algorithm. Modify the Mergesort algorithm bellow to a stable sorting algorithm.

Problem: Merge the two sorted subarrays of S created in Mergesort 2.
Inputs: indices low, mid, and high, and the subarray of S indexed from low to high. The keys in array slots from low to mid are already sorted in nondecreasing order, as are the keys in array slots from mid + 1 to high.
Outputs: the subarray of S indexed from low to high containing the keys in nondecreasing order.

void merge2 (index low, index mid, index high) index i, j keytype Ul low.. high]; // A local array needed for the merging = low; j = mid +1; k = low; while i mid &&j; high)\\ else SIj]; if i > mid move Sjthrough S[high to U kthrough U[high ]; else move S[i] through SImid to Uk] through Ulhigh]; move Ulow] through U[high] to S[low] through S[high

Solution

A sorting algorithm is usually considered to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array.This can happen for merget sort as well in the following ways.

For the mergesort to be stable we will follow the following function

MergeSort(arr[], low, high) where low is the left most element of array

and the high is the right most element of the array

If high > l                                            

     1.Firstly we will find the middle point in order to divide the array

into two halves:

             middle mid = (low+high)/2

    2. The second step is to call mergeSort for first half:  

             Call mergeSort(arr, low, mid)

     3. The next step is to call mergeSort for second half:

             Call mergeSort(arr, mid+1, right)

     4. Finally we will merge the two halves sorted in step 2 and 3:

             Call merge(arr, low, mid, right)

// This function Merges two subarrays of array[]. The first subarray is array[l..mid],The Second subarray is array[mid+1..high]

void merge(int array[], int low, int mid, int high)

{

    int i, j, k;

    int n1 = mid - low + 1;

    int n2 = high - mid;

    /* now we will c create temp arrays */

    int Left[n1], Right[n2];

    /* firsly we will copy data to temp arrays Left[] and Right[] */

    for (i = 0; i < n1; i++)

        Left[i] = array[l + i];

    for (j = 0; j < n2; j++)

        Right[j] = array[m + 1+ j];

    /* The next step is to merge the temp arrays back into arry[l..high]*/

    i = 0; //This is the initial index of first subarray

    j = 0; //This is the Initial index of second subarray

    k = l; // This is the Initial index of merged subarray

    while (i < n1 && j < n2)

    {

        if (Left[i] <= Right[j])

        {

            array[k] = Left[i];

            i++;

        }

        else

        {

            array[k] = Right[j];

            j++;

        }

        k++;

    }

    /* Now we will copy the remaining elements of Left[], if there

       are any */

    while (i < n1)

    {

        arry[k] = Left[i];

        i++;

        k++;

    }

    /* Next we will copy the remaining elements of Right[], if there

       are any */

    while (j < n2)

    {

        array[k] = Right[j];

        j++;

        k++;

    }

}

                                                                                                        

/* now we have , low is for left index and high is right index of the

   sub-array of array to be sorted */

void mergeSort(int array[], int low, int high)

{

    if (low < high)

    {

        

        int mid = l+(high-l)/2;

        // Now we will sort the first and second halves

        mergeSort(array, low, mid);

        mergeSort(array, mid+1, high);

        merge(array, low, mid, high);

    }

}

/*This is the Function to print an array */

void printArray(int B[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf(\"%d \", B[i]);

    printf(\"\ \");

}

/* Now we have the driver program to test above functions */

int main()

{

    int array[] = {12, 13, 11, 3, 4, 5};

    int array_size = sizeof(array)/sizeof(array[0]);

    printf(\"The given array is \ \");

    printArray(array, array_size);

    mergeSort(array, 0, array_size - 1);

    printf(\"\ The Sorted array is \ \");

    printArray(arry, arry_size);

    return 0;

}

OUTPUT:

The Given array is: 12   13   11    3    4   5

TheSorted array is: 3    4    5     11   12   13