Skip to content

Instantly share code, notes, and snippets.

@tomleo
Last active December 13, 2015 20:19
Show Gist options
  • Save tomleo/4969355 to your computer and use it in GitHub Desktop.
Save tomleo/4969355 to your computer and use it in GitHub Desktop.
Implementation of merge sort in C++
CPPFLAGS=-g -c -std=c++0x
LDFLAGS=-g
RM=rm -f
SOURCES=merge-sort.cc
OBJECTS=merge-sort.o
all: merge-sort
merge-sort: $(OBJECTS)
$(CXX) $(LDFLAGS) -o merge-sort $(OBJECTS)
merge-sort.o: merge-sort.cc merge-sort.h
$(CXX) $(CPPFLAGS) merge-sort.cc
clean:
$(RM) $(OBJECTS)
#include "merge-sort.h"
using std::cout;
using std::endl;
int* merge2(int *A, int len_A, int *B, int len_B) {
/*
*
* Takes arrays A and B as input, outputs sorted array containing all the
* elements from A and B.
*
* Requirements: A and B must be sorted arrays
*
*/
int N = len_A + len_B;
int *C = new int[N];
int i=0;
int j=0;
int k=0;
//Populate array C with elements in sorted order from arrays A and B
for(; k<N; k++){
if ((i>=len_A) || (j>=len_B)){
break;
}
if (A[i] < B[j]) {
C[k] = A[i];
i++;
}
else {
C[k] = B[j];
j++;
}
}
//Add leftover elements in A
for(;i<len_A; i++) {
C[k] = A[i];
k++;
}
//Add leftover elements in B
#include<iostream>
#include<cstdlib>
//MergeSort algorithm implementation
int* merge2(int *A, int len_A, int *B, int len_B);
int* sort2(int *A, int len_A);
//Utility Functions
int* genArray(size_t size);
void printArray(int *array, int l);
void testMergeSort();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment