Question

4. Write out the pseudocode for when Merge-Sort is stable based on the information given below:

Comparision Based Stable Sorts such as Merge Sort maintain stability by ensuring that Element A[ j ] comes before A[ i ] if and only if A[ j ] < A[ i ], here i, j are indices and i < j. The relative order is preserved if A[ i ] comes before A[ j ].

Mergesort is stable, provided its implementation employs the comparison ≤ in merging. Indeed, assume that we have two elements of the same value in positions i and j, i < j, in a subarray before its two (sorted) halves are merged. If these two elements are in the same half of the subarray, their relative ordering will stay the same after the merging because the elements of the same half are processed by the merging operation in the FIFO fashion. Consider now the case when A[ i ] is in the first half while A[ j ] is in the second half. A[ j ] is placed into the new array either after the first half becomes empty (and, hence, A[ i ] has been already copied into the new array) or after being compared with some key k > A[ j ] of the first half. In the latter case, since the first half is sorted before the merging begins, A[ i ] = A[ j ] < k cannot be among the unprocessed elements of the first half. Hence, by the time of this comparison, A[ i ] has been already copied into the new array and therefore will precede A[ j ] after the merging operation is completed.

Answer 1

CODE FOR STABLE MERGE SORT

1. PseudoCode/Algorithm for Merge Sort

procedure mergesort( var a as array )
   if ( n == 1 ) return a

   var l1 as array = a[0] ... a[n/2]
   var l2 as array = a[n/2+1] ... a[n]

   l1 = mergesort( l1 )
   l2 = mergesort( l2 )

   return merge( l1, l2 )
end procedure

procedure merge( var a as array, var b as array )

   var c as array
   while ( a and b have elements )
      if ( a[0] > b[0] )
         add b[0] to the end of c
         remove b[0] from b
      else
         add a[0] to the end of c
         remove a[0] from a
      end if
   end while
   
   while ( a has elements )
      add a[0] to the end of c
      remove a[0] from a
   end while
   
   while ( b has elements )
      add b[0] to the end of c
      remove b[0] from b
   end while
   
   return c
        
end procedure

----------------------------------------------------------------------------------------------------------------------------------------------------------

2. C++ code for merge sort

#include<iostream> 
using namespace std; 
  
// Merges two subarrays of arr[]. 
// First subarray is arr[l..m] 
// Second subarray is arr[m+1..r] 
void merge(int arr[], int l, int m, int r) 
{ 
    int n1 = m - l + 1; 
    int n2 = r - m; 
  
    // Create temp arrays  
    int L[n1], R[n2]; 
  
    // Copy data to temp arrays L[] and R[]  
    for(int i = 0; i < n1; i++) 
        L[i] = arr[l + i]; 
    for(int j = 0; j < n2; j++) 
        R[j] = arr[m + 1 + j]; 
  
    // Merge the temp arrays back into arr[l..r] 
      
    // Initial index of first subarray 
    int i = 0;  
      
    // Initial index of second subarray 
    int j = 0;  
      
    // Initial index of merged subarray 
    int k = l; 
      
    while (i < n1 && j < n2) 
    { 
        if (L[i] <= R[j])  
        { 
            arr[k] = L[i]; 
            i++; 
        } 
        else 
        { 
            arr[k] = R[j]; 
            j++; 
        } 
        k++; 
    } 
  
    // Copy the remaining elements of 
    // L[], if there are any  
    while (i < n1)  
    { 
        arr[k] = L[i]; 
        i++; 
        k++; 
    } 
  
    // Copy the remaining elements of 
    // R[], if there are any  
    while (j < n2) 
    { 
        arr[k] = R[j]; 
        j++; 
        k++; 
    } 
} 
  
// l is for left index and r is  
// right index of the sub-array 
// of arr to be sorted */ 
void mergeSort(int arr[], int l, int r) 
{ 
    if (l < r) 
    { 
          
        // Same as (l+r)/2, but avoids  
        // overflow for large l and h 
        int m = l + (r - l) / 2; 
  
        // Sort first and second halves 
        mergeSort(arr, l, m); 
        mergeSort(arr, m + 1, r); 
  
        merge(arr, l, m, r); 
    } 
} 
  
// UTILITY FUNCTIONS  
// Function to print an array  
void printArray(int A[], int size) 
{ 
    for(int i = 0; i < size; i++) 
        cout << A[i] << " "; 
} 
  
// Driver code 
int main() 
{ 
    int arr[] = { 12, 11, 13, 5, 6, 7 }; 
    int arr_size = sizeof(arr) / sizeof(arr[0]); 
  
    cout << "Given array is \n"; 
    printArray(arr, arr_size); 
  
    mergeSort(arr, 0, arr_size - 1); 
  
    cout << "\nSorted array is \n"; 
    printArray(arr, arr_size); 
    return 0; 
} 

----------------------------------------------------------------------------------------------------------------------------------------------------------

ANALYSIS ->

Worst complexity: n*log(n)

Average complexity: n*log(n)

Best complexity: n*log(n)

Space complexity: n

----------------------------------------------------------------------------------------------------------------------------------------------------------

If you come across any doubt feel free to ask in the comments below.

Do give the solution a thumbs up if you are satisfied with it.

Thank You.

ALL THE BEST!