1. Problem Description

This is a problem to sort a given list of integers in ascending order. It is solved using the
Merge Sort algorithm. Merge sort is a type of divide and conquer algorithm that recursively divides the given list into two sub-lists, sorts each of them, and then merges them back into a single list.

2. Problem Input

– The first input is the number of integers to be sorted N (1 ≤ N ≤ 106).
– The second input consists of N integers. These integers may include any negative and
positive values, and each integer is within the range of 32-bit integers.

3. Problem Output

Output the sorted integer list, with each integer separated by a space.

4. Algorithm Description

The main idea of merge sort is to divide the array into two parts at the midpoint, recursively sort each part, and then merge the two sorted parts to create the final sorted array.

4.1 Algorithm Steps

  1. If the size of the array is 1 or less, it is already sorted, so return that array.
  2. Split the array into two sub-arrays based on the midpoint index.
  3. Recursively call merge sort on each sub-array.
  4. Merge the two sorted sub-arrays to form one sorted array.

5. Code Implementation


#include <iostream>
#include <vector>

using namespace std;

// Function to merge two arrays
void merge(vector &arr, int left, int mid, int right) {
    int n1 = mid - left + 1; // Size of left array
    int n2 = right - mid;    // Size of right array
    vector L(n1), R(n2); // Create sub-arrays

    // Store values in sub-arrays
    for (int i = 0; i < n1; ++i)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j)
        R[j] = arr[mid + 1 + j];

    // Merge sub-arrays
    int i = 0; // Index i for L
    int j = 0; // Index j for R
    int k = left; // Index k for arr

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Process remaining elements
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Merge sort function
void mergeSort(vector &arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2; // Calculate midpoint

        mergeSort(arr, left, mid); // Sort left array
        mergeSort(arr, mid + 1, right); // Sort right array

        merge(arr, left, mid, right); // Merge two arrays
    }
}

int main() {
    int N;
    cin >> N; // Input number of integers
    vector arr(N);

    for (int i = 0; i < N; i++) {
        cin >> arr[i]; // Input integer list
    }

    mergeSort(arr, 0, N - 1); // Call merge sort

    // Output result
    for (int i = 0; i < N; i++) {
        cout << arr[i];
        if (i < N - 1) cout << " "; // Space separation
    }
    cout << endl;

    return 0;
}

6. Complexity Analysis

The time complexity of merge sort is O(N log N), where N is the size of the array.
This is due to the depth of log N from the array being divided in half,
and N time required to merge at each level.
Therefore, merge sort guarantees O(N log N) performance in both average and worst-case scenarios.

The space complexity relates to the additional memory used,
as merge sort generates two sub-arrays, requiring O(N) additional memory.

7. Conclusion

The merge sort algorithm is stable and effective for sorting large amounts of data.
It can be utilized in various programming tasks and problem-solving scenarios.
Unlike ultra-fast sorting algorithms (e.g., Quick Sort),
merge sort is characterized by consistent performance and simple implementation, making it popular in many situations.

8. Additional Practice Problems

Please solve the following problems.

  1. Write a program to find the mode in a given list.
  2. Write a program using merge sort to merge two sorted arrays into one sorted array.