mergeSort

gistfile1.txt

void merge(int input[], int left, int right, int mid) {
  int leftIt = left;
  int rightIt = mid+1;
  int temp[right];
  int cnt = 0;
  
  while(leftIt<=mid && rightIt<=right) {
    if(input[leftIt] < input[rightIt]) {
      temp[cnt++] = input[leftIt++];
    } else {
      temp[cnt++] = input[rightIt++];
    }
  }
  
  while(leftIt <= mid) temp[cnt++] = input[leftIt++];
  while(rightIt <= right) temp[cnt++] = input[rightIt++];
  
  for(int i=left ; i <= right ; i++) input[i] = temp[i-left];
}

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


void quickSort(int input[], int left, int right) {
  int leftIt = left;
  int rightIt = right;
  int pivot = input[right];
  
  while(leftIt < rightIt) {
    while(input[leftIt] < pivot) leftIt++;
    while(input[rightIt] > pivot) rightIt--;
    
    if(leftIt < rightIt) {
      int temp = input[leftIt];
      input[leftIt] = input[rightIt];
      input[rightIt] = temp;
      
      leftIt++;
      rightIt--;
    } else if(leftIt == rightIt) {
      leftIt++;
      rightIt--;
    }
  }
  
  if(left < rightIt) quickSort(input, left, rightIt);
  if(leftIt < right) quickSort(input, leftIt, right);
}