CS201: Elementary Data Structures

Insertion Sort:

/* insertion sort ascending order */
 
#include 
 
int main()
{
  int n, array[1000], c, d, t;
 
  printf("Enter number of elements\n");
  scanf("%d", &n);
 
  printf("Enter %d integers\n", n);
 
  for (c = 0; c < n; c++) {
    scanf("%d", &array[c]);
  }
 
  for (c = 1 ; c <= n - 1; c++) {
    d = c;
 
    while ( d > 0 && array[d] < array[d-1]) {
      t          = array[d];
      array[d]   = array[d-1];
      array[d-1] = t;
 
      d--;
    }
  }
 
  printf("Sorted list in ascending order:\n");
 
  for (c = 0; c <= n - 1; c++) {
    printf("%d\n", array[c]);
  }
 
  return 0;
}

Merge Sort:

// Declare/initialize any useful variables here, including the temporary array 
// to merge values into and then copy back into the parameter array.

/*
while the temporary array is not filled
if there are no more values in the left part of a,
move next value from right part of a into next index of the temporary array otherwise, if there are no more values in the right part of a,
move next value from left part of a into next index of the temporary array otherwise (values in each part) compare the first value in each part
move smallest value from a into next index of the temporary array
Copy all values from the temporary array back into a, starting at left_low
*/

void merge_sort(int a[], int length) {
    merge_sort(a, 0, length-1);
}

void merge_sort(int a[], int low, int high) {
    if (low >= high)                  //Base case: 1 value to sort->sorted
      return;                         //(0 possible only on initial call)
    else {
      int mid = (low + high)/2;       //Approximate midpoint*
      merge_sort(a, low, mid);        //Sort low to mid part of array
      merge_sort(a, mid+1, high);     //Sort mid+1 to high part of array
      merge(a, low, mid, mid+1,high); //Merge sorted subparts of array
    }
}

void merge(int a[], int left_low, int left_high, int right_low, int right_high) 
{ 
    int length = right_high-left_low+1;
    int temp[length];
    int left = left_low;
    int right = right_low;
    for (int i = 0; i < length; ++i) { 
        if (left > left_high)
            temp[i] = a[right++];
        else if (right > right_high)
            temp[i] = a[left++];
        else if (a[left] <= a[right])
            temp[i] = a[left++];
        else
            temp[i] = a[right++]; 
    }
    
    for (int i=0; i< length; ++i) 
        a[left_low++] = temp[i];
}

Source: http://www.programmingsimplified.com/c/source-code/c-program-insertion-sort and https://gist.githubusercontent.com/kbendick/1de4f311e2a780339eb3/raw/f65b82b7a055806004af4962290adb5c401335e1/mergesort.cpp
 This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.