Created
October 9, 2013 01:40
-
-
Save chihuahua/6894823 to your computer and use it in GitHub Desktop.
Merge Sort
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * Merge sort. | |
| * | |
| * By Chi Zeng ([email protected]) and compatriots who cared enough about CS50 to | |
| * come to section. | |
| * Oct. 8, 2013 | |
| */ | |
| #include <stdio.h> | |
| #include <stdlib.h> | |
| #include <string.h> | |
| // sorts an array using merge sort. | |
| void sort(int* arr, int length); | |
| // helper function for sort that uses recursion. don't call directly. | |
| // sorts array from [begin, end). | |
| void sortHelper(int* arr, int begin, int end); | |
| // our first subarray: [begin, mid); our second subarray: [mid, end) | |
| void merge(int* arr, int begin, int mid, int end); | |
| // prints out an array of integers. | |
| void printArray(int* arr, int length); | |
| int main() | |
| { | |
| // check if sort works. | |
| int arr[5] = {7, 8, 4, 2, 1}; | |
| sort(arr, 5); | |
| printArray(arr, 5); | |
| // try using an even number of ints. | |
| int arr2[4] = {9, 8, 4, 2}; | |
| sort(arr, 4); | |
| printArray(arr, 4); | |
| // how about just 1 int? | |
| int arr3[1] = {42}; | |
| sort(arr, 1); | |
| printArray(arr, 1); | |
| // how about ... an empty array? | |
| int arr4[0] = {}; | |
| sort(arr, 0); | |
| printArray(arr, 0); | |
| return 0; | |
| } | |
| void sort(int* arr, int length) | |
| { | |
| // defer to our helper function that calls itself recursively. | |
| sortHelper(arr, 0, length); | |
| } | |
| void sortHelper(int* arr, int begin, int end) | |
| { | |
| if (end - begin < 2) | |
| { | |
| // already done sorting. | |
| return; | |
| } | |
| // find the midpoint so we can divide our array in half. | |
| int mid = begin + (end - begin) / 2; | |
| // the left subrarray consists of elements with indices in [begin, mid). | |
| sortHelper(arr, begin, mid); | |
| sortHelper(arr, mid, end); | |
| // merge the sorted subarrays. | |
| merge(arr, begin, mid, end); | |
| } | |
| void merge(int* arr, int begin, int mid, int end) | |
| { | |
| int leftSize = mid - begin; | |
| int rightSize = end - mid; | |
| int leftnumBytes = leftSize * sizeof(int); | |
| int* left = malloc(leftnumBytes); | |
| if (left == NULL) | |
| { | |
| // we lack enough memory. :( | |
| exit(-1); | |
| } | |
| // make a buffer for the left subarray. | |
| memcpy(left, arr + begin, leftnumBytes); | |
| int rightNumBytes = rightSize * sizeof(int); | |
| int* right = malloc(rightNumBytes); | |
| if (right == NULL) | |
| { | |
| // we lack enough memory. :( | |
| exit(-1); | |
| } | |
| // make a buffer for the right subarray. | |
| memcpy(right, arr + mid, rightNumBytes); | |
| int overallIndex = begin; | |
| int leftIndex = 0; | |
| int rightIndex = 0; | |
| while (leftIndex < leftSize && rightIndex < rightSize) | |
| { | |
| if (left[leftIndex] < right[rightIndex]) | |
| { | |
| // pull down the item from the left array. | |
| arr[overallIndex] = left[leftIndex]; | |
| ++leftIndex; | |
| } | |
| else | |
| { | |
| // pull down the item from the right array. | |
| arr[overallIndex] = right[rightIndex]; | |
| ++rightIndex; | |
| } | |
| // increase our index into the original array. | |
| ++overallIndex; | |
| } | |
| // pull down items still in the left subarray. | |
| for (; leftIndex < leftSize; ++leftIndex, ++overallIndex) | |
| { | |
| arr[overallIndex] = left[leftIndex]; | |
| } | |
| // pull down items still in the right subarray. | |
| for (; rightIndex < rightSize; ++rightIndex, ++overallIndex) | |
| { | |
| arr[overallIndex] = right[rightIndex]; | |
| } | |
| // free the buffers of heap memory we used. | |
| free(left); | |
| free(right); | |
| } | |
| void printArray(int* arr, int length) | |
| { | |
| for (int i = 0; i < length; ++i) | |
| { | |
| printf("%i ", arr[i]); | |
| } | |
| // add a new line after an array is printed. | |
| printf("\n"); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment