What is the main idea and advantages of the merge sort algorithm?

Merge Sort algorithm is based on the 'divide and conquer' principle. It recursively divides the original array into two halves, sorts each half, and then merges the two sorted parts into one sorted array.

Advantages:

• Stability: maintains the order of equal elements.
• Guaranteed runtime of O(n log n) in the worst, average, and best cases.
• Suitable for sorting large volumes of data and external sorting.

Example in Java:

void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void merge(int[] arr, int left, int mid, int right) {
    // Logic for merging two sorted subarrays
}