The Algorithms logo
The Algorithms
关于捐赠

Mergesort

P
b
M
m
M
N
S
A
H
p
I
以及1个贡献者
/**
 * @file
 * @brief Implementation of [merge
 * sort](https://en.wikipedia.org/wiki/Merge_sort) algorithm
 */
#include <stdio.h>
#include <stdlib.h>

/**
 * @addtogroup sorting Sorting algorithms
 * @{
 */
/** Swap two integer variables
 * @param [in,out] a pointer to first variable
 * @param [in,out] b pointer to second variable
 */
void swap(int *a, int *b)
{
    int t;
    t = *a;
    *a = *b;
    *b = t;
}

/**
 * @brief Perform merge of segments.
 *
 * @param a array to sort
 * @param l left index for merge
 * @param r right index for merge
 * @param n total number of elements in the array
 */
void merge(int *a, int l, int r, int n)
{
    int *b = (int *)malloc(n * sizeof(int)); /* dynamic memory must be freed */
    if (b == NULL)
    {
        printf("Can't Malloc! Please try again.");
        exit(EXIT_FAILURE);
    }
    int c = l;
    int p1, p2;
    p1 = l;
    p2 = ((l + r) / 2) + 1;
    while ((p1 < ((l + r) / 2) + 1) && (p2 < r + 1))
    {
        if (a[p1] <= a[p2])
        {
            b[c++] = a[p1];
            p1++;
        }
        else
        {
            b[c++] = a[p2];
            p2++;
        }
    }

    if (p2 == r + 1)
    {
        while ((p1 < ((l + r) / 2) + 1))
        {
            b[c++] = a[p1];
            p1++;
        }
    }
    else
    {
        while ((p2 < r + 1))
        {
            b[c++] = a[p2];
            p2++;
        }
    }

    for (c = l; c < r + 1; c++) a[c] = b[c];

    free(b);
}

/** Merge sort algorithm implementation
 * @param a array to sort
 * @param n number of elements in the array
 * @param l index to sort from
 * @param r index to sort till
 */
void merge_sort(int *a, int n, int l, int r)
{
    if (r - l == 1)
    {
        if (a[l] > a[r])
            swap(&a[l], &a[r]);
    }
    else if (l != r)
    {
        merge_sort(a, n, l, (l + r) / 2);
        merge_sort(a, n, ((l + r) / 2) + 1, r);
        merge(a, l, r, n);
    }

    /* no change if l == r */
}
/** @} */

/** Main function */
int main(void)
{
    int *a, n, i;
    printf("Enter Array size: ");
    scanf("%d", &n);
    if (n <= 0) /* exit program if arraysize is not greater than 0 */
    {
        printf("Array size must be Greater than 0!\n");
        return 1;
    }
    a = (int *)malloc(n * sizeof(int));
    if (a == NULL) /* exit program if can't malloc memory */
    {
        printf("Can't Malloc! Please try again.");
        return 1;
    }
    for (i = 0; i < n; i++)
    {
        printf("Enter number[%d]: ", i);
        scanf("%d", &a[i]);
    }

    merge_sort(a, n, 0, n - 1);
    printf("Sorted Array: ");
    for (i = 0; i < n; i++)
    {
        printf("%d ", a[i]);
    }
    printf("\n");

    free(a);

    return 0;
}
关于这个算法

Problem Statement

Given an array of n elements, write a function to sort the array

Approach

  • Find a mid point and divide the array into to halves based on the mid point
  • Recursively call the merge sort function for both the halves
  • Merge the two sorted halves to get the sorted array

Time Complexity

Best case - O(n log n)
Average - O(n log n)
Worst case - O(n log n)

Space Complexity

O(n)

Example 1

arr = [1, 3, 9, 5, 0, 2]  

Divide the array in two halves [1, 3, 9] and [5, 0, 2]

Recursively call merge sort function for both these halves which will provide sorted halves
=> [1, 3, 9] & [0, 2, 5]

Now merge both these halves to get the sorted array [0, 1, 2, 3, 5, 9]

Example 2

arr = [1, 9, 2, 5, 7, 3, 6, 4]  

Divide the array into two halves [1, 9, 2, 5] and [7, 3, 6, 4]

As you can see that the above two halves are not yet sorted, so divide both of them into two halves again.

This time we get four arrays as [1, 9], [2, 5], [7, 3] and [6, 4].

We see that the last two arrays are again not sorted, so we divide them again into two halves and we will get [7], [3], [6], and [4].

Since an array of a single element is sorted, we now have all the arrays sorted, now we only need to merge them appropriately.

First, the arrays of one element will be merged as they were divided in last, and are at top of the recursion stack, so we get [3,7] and [4,6].

Now the merge will occur accordingly to the recursion stack, [1, 9] and [2, 5] will be merged and will make [1, 2, 5, 9].

Similarly [3, 7] and [4, 6] will be merged and made [3, 4, 6, 7].

At the next stack level [1, 2, 5, 9] and [3, 4, 6, 7] will be merged and we will get the final sorted array as [1, 2, 3, 4, 5, 6, 7, 9].

Video Explanation

A CS50 video explaining the Merge Sort Algorithm