If I take a sorting algorithm written in C code and port it to C++, will it be faster? Or, not slower? Hmm… Lets find out

Introduction

<—- WIP —->

Merge Sort

C Code

#include <stdio.h>
#include <stdlib.h>

void merge(int *arr, long long l, long long m, long long r) {
  long long i, j, k;
  long long n1 = m - l + 1;
  long long n2 = r - m;

  long long size_n1 = sizeof(int) * n1;
  long long size_n2 = sizeof(int) * n2;
  int *L = (int*)malloc(size_n1);
  int *R = (int*)malloc(size_n2);

  for(i = 0; i < n1; i++) L[i] = arr[l + i];
  for(j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

  i = 0;
  j = 0;
  k = l;

  while(i < n1 && j < n2) {
    if(L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    }
    else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  while(i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while(j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }

  free(L);
  free(R);
}

void merge_sort(int *arr, long long l, long long r) {
  if(l < r) {
    long long m = l + (r - l) / 2;

    merge_sort(arr, l, m);
    merge_sort(arr, m+1, r);

    merge(arr, l, m, r);
  }
}

void print_array(int arr[], int size) {
  int i = 0;
  for(i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main() {
  long long len = 1 << 28;
  long long size = len * sizeof(int);
  int* arr = (int*)malloc(size);
  for(long long i = 0; i < len; i++) {
    arr[i] = rand() % 100 + 1;
  }

  printf("Given array is\n");
//  print_array(arr, arr_size);
  merge_sort(arr, 0, len - 1);

  printf("Sorted array is\n");
//  print_array(arr, arr_size);
  return 0;
}

C++ Code

#include <stdio.h>
#include <stdlib.h>

void merge(int *arr, long long l, long long m, long long r) {
  long long i, j, k;
  long long n1 = m - l + 1;
  long long n2 = r - m;

  long long size_n1 = sizeof(int) * n1;
  long long size_n2 = sizeof(int) * n2;
  int *L = (int*)malloc(size_n1);
  int *R = (int*)malloc(size_n2);

  for(i = 0; i < n1; i++) L[i] = arr[l + i];
  for(j = 0; j < n2; j++) R[j] = arr[m + 1 + j];

  i = 0;
  j = 0;
  k = l;

  while(i < n1 && j < n2) {
    if(L[i] <= R[j]) {
      arr[k] = L[i];
      i++;
    }
    else {
      arr[k] = R[j];
      j++;
    }
    k++;
  }

  while(i < n1) {
    arr[k] = L[i];
    i++;
    k++;
  }

  while(j < n2) {
    arr[k] = R[j];
    j++;
    k++;
  }

  free(L);
  free(R);
}

void merge_sort(int *arr, long long l, long long r) {
  if(l < r) {
    long long m = l + (r - l) / 2;

    merge_sort(arr, l, m);
    merge_sort(arr, m+1, r);

    merge(arr, l, m, r);
  }
}

void print_array(int arr[], int size) {
  int i = 0;
  for(i = 0; i < size; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

int main() {
  long long len = 1 << 28;
  long long size = len * sizeof(int);
  int* arr = (int*)malloc(size);
  for(long long i = 0; i < len; i++) {
    arr[i] = rand() % 100 + 1;
  }

  printf("Given array is\n");
//  print_array(arr, arr_size);
  merge_sort(arr, 0, len - 1);

  printf("Sorted array is\n");
//  print_array(arr, arr_size);
  return 0;
}
real Compilation (s) Runtime (s)
C Code 0m0.325s 1m10.573s
C++ Code 0m10.015s 6m35.827s

Configuration

C Compiler: clang CXX Compiler: clang++ Opt used:

Aditya Atluri

Works on GPUs. Programming models, optimizations, power efficiency, hardware design.

jekyll jekyllrb


Published