居然花了一個禮拜寫merge sort

服替代役有很多無聊的時間，所以我就在公家電腦灌了cygwin練習用gnu提供的工具(e.g. g++, make等) 來寫程式。一開始挑戰的是我大一的時候寫不出來的merge sort，讀入random.txt並且排列出來，最多排列1024個數字。

merge_sort.cpp

#include "function.h"

int main()

{
        fstream fstr; 
        int i=0; 
        int rand[1024]; 
        int temp[1024]; 
        int randn; 
        
        cout<<"unsorted:"; 
        fstr.open("random.txt", ios::in); 
                while(fstr>>rand[i]){

                cout<<rand[i]<<setw(2); 
                i++; 
        }

        cout<<" # of rands:"<<i<<endl; 
        randn=i; 

        merge_sort(rand, randn, temp); 

        cout<<"sorted list: "; 
        for(i=0; i<randn; i++) 
                cout<<rand[i]<<" "; 

        fstr.close(); 

        return 0; 

}

function.cpp

#include "function.h"

void merge_sort(int* unsorted, int size, int* sorted)

//sort the unsorted array
{
        int mid; 
        int *left, *right; 
        int i; 
        
        if(size<2) return; 

        mid=(size+1)/2; 
        left=unsorted;

        right=unsorted+mid; 

        //printf("[%d, %d]\n", *left, *right); 
        
        merge_sort(left, mid, sorted); 
        merge_sort(right, size-mid, sorted); 
        
        for(i=0; i<size; i++)   printf("%d,", unsorted[i]); 
        printf(" | "); 
        merge(left, mid, right, size-mid, sorted); 
        for(i=0; i<size; i++)   printf("%d,", unsorted[i]); 
        printf("\n"); 


}

void merge(int* left, int sizel, int* right, int sizer, int* sorted)

{
        //printf("left=%d, right=%d, sizel=%d, sizer=%d ", *left, *right, sizel, sizer); 
        int i=0, j=0, k=0; 
        while(i<sizel && j<sizer)

        {
                if(*(left+i)<*(right+j)) {

                        sorted[k]=*(left+i); 
                        i++; 
                }

                else{
                        sorted[k]=*(right+j);

                        j++; 
                }
                k++; 

        }

        if(i==sizel) 
                memcpy(sorted+k, right+j, sizeof(int)*(sizer-j)); 
        if(j==sizer)

                memcpy(sorted+k, left+i, sizeof(int)*(sizel-i)); 

        memcpy(left, sorted, sizeof(int)*(sizel+sizer)); 
        
        //for(i=0; i<sizel+sizer; i++)  printf("%d,", sorted[i]); 

        //printf("\n"); 
}

function.h

#ifndef FUNCTION_H
#define FUNCTION_H

#include <iostream>
#include <iomanip>

#include <fstream> 
using namespace std; 
#include <string.h>


void merge_sort(int* unsorted, int size, int* sorted); 

void merge(int* left, int sizel, int* right, int sizer, int* sorted); 


#endif