/* * File: sort.c * ------------ * This file implements the sort.h interface using the merge * sort algorithm. */#include <stdio.h>#include "genlib.h"#include "sort.h"/* Private function prototypes */static void Merge(int array[], int arr1[], int n1,                               int arr2[], int n2);/* * Function: SortIntegerArray * -------------------------- * This implementation uses an algorithm called merge sort, which * consists of the following steps: * * (1)  Divide the array into two halves. * (2)  Sort each half recursively. * (3)  Recombine the sorted pieces by calling the Merge function. */void SortIntegerArray(int array[], int n){    int i, n1, n2;    int *arr1, *arr2;    if (n > 1) {        n1 = n / 2;        n2 = n - n1;        arr1 = NewArray(n1, int);        arr2 = NewArray(n2, int);        for (i = 0; i < n1; i++) arr1[i] = array[i];        for (i = 0; i < n2; i++) arr2[i] = array[n1 + i];        SortIntegerArray(arr1, n1);        SortIntegerArray(arr2, n2);        Merge(array, arr1, n1, arr2, n2);        FreeBlock(arr1);        FreeBlock(arr2);    }}/* * Function: Merge * Usage: Merge(array, arr1, n1, arr2, n2); * ---------------------------------------- * This function merges two sorted arrays (arr1 and arr2) into a * single array.  Because the input arrays are sorted, the Merge * implementation can always select the first unused element in * one of the input arrays to fill the next position in array. */static void Merge(int array[], int arr1[], int n1,                               int arr2[], int n2){    int p, p1, p2;    p = p1 = p2 = 0;    while (p1 < n1 && p2 < n2) {        if (arr1[p1] < arr2[p2]) {            array[p++] = arr1[p1++];        } else {            array[p++] = arr2[p2++];        }    }    while (p1 < n1) array[p++] = arr1[p1++];    while (p2 < n2) array[p++] = arr2[p2++];}