やっとデバッグしたハッシュバケツ挿入ソート貼る

とりあえずやり切った、挿入ソートの部分を大きくすると時間がのびた所までは確認した、きたない

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

struct NVtab
{
  int num;
  struct NVtab *next;
};

enum
  {
    INIT = 4096,
    GROW = 2
  };

char* fileGetLine(FILE*);
static int endofline(FILE*, int);
void mysort(int*,int);
int main(int args, char *argv[])
{
  int i;
  char *line = NULL;
  int *nums = NULL;
  FILE *f;
  if(argv[1] == NULL)
    {
      f = stdin;
    }
  else if((f = fopen(argv[1], "r")) == NULL)
    {
      fprintf(stderr, "ファイルがないよ\n");
      exit(1);
    }
  for (i = 0; (line = fileGetLine(f)) != NULL; i++)
    {
      nums = realloc(nums, sizeof(int) * (i+1));

      nums[i] =  atoi(line);

      free(line);
    }

  if(argv[1] != NULL)
    {
      fclose(f);
    }

  mysort(nums, i);

  free(nums);

  return 0;
}
int hash(int num, int nhash)
{
  int temp;
  
  temp = ((double)num / INT_MAX) * (nhash - 1);

  return temp;
}


void mysort(int *nums, int len)
{
  int i, j;
  int h;
  int maxchain;
  int maenum;
  int nhash;
  struct NVtab **val;
  struct NVtab *newchain;
  struct NVtab *tmpchain;
  struct NVtab *nextchain;

  nhash = 1000 * 1000 * 10;

  val = (struct NVtab**)malloc(sizeof(struct NVtab*) * nhash);  
  for(i = 0; i < nhash; i++)
    {
      val[i] = NULL;
    }

  for(i = 0; i < len; i++)
    {

      h = hash(nums[i],nhash);
      newchain = (struct NVtab*)malloc(sizeof(struct NVtab));

      if(val[h] == NULL)
	{
	  newchain->next = NULL;
	  val[h] = newchain;
	}
      else if(val[h]->num > nums[i])
	{
	  newchain->next = val[h];
	  val[h] = newchain;
	}
      else
	{
	  nextchain = val[h]->next;
	  for(tmpchain = val[h]; tmpchain != NULL; tmpchain = tmpchain->next)
	    {
	      if(nextchain == NULL)
		{
		  newchain->next = NULL;
                  tmpchain->next = newchain;
                  break;
		}
	      
	      if(nums[i] <= nextchain->num)
		{
		  newchain->next = tmpchain->next;
		  tmpchain->next = newchain;
		  break;
		}

	      nextchain = nextchain->next;
	    }
	}
      newchain->num = nums[i];
    }
    
  maenum = -1;
  for(i = 0; i < nhash; i++)
    {
      for(tmpchain = val[i]; tmpchain != NULL; tmpchain = tmpchain->next)
	{
	  if(!(maenum <= tmpchain->num))
	    {
	      fprintf(stderr,"%d\n", j);
	      for(tmpchain = val[i]; tmpchain != NULL; tmpchain = tmpchain->next)
		{
		  fprintf(stderr,"%d\t%d\n", j, tmpchain->num);
		}
	      exit(1);
	    }
	  maenum = tmpchain->num;
	  printf("%d\n",tmpchain->num);
	}
    }
}

char* fileGetLine(FILE *fin)
{
  int i, c;
  int maxline = INIT;
  char *line = (char*)malloc (sizeof(char) * maxline);

  for (i = 0;(c = getc(fin)) != EOF && !(endofline(fin, c)); i++)
    {
      if (i > maxline)
	{
	  maxline *= GROW;
	  line = (char*) realloc(line, sizeof(char) * (maxline + 1));
	}
      line[i] = (char)c;
      line[i+1] = '\0';
    }

  return (c == EOF && i == 0) ? NULL : line;
}

static int endofline(FILE *fin, int c)
{
  int eol;
  eol = (c == '\r' || c == '\n');

  if (c == '\r')
    {
      c = getc(fin);
      if (c != '\n' && c != EOF)
	{
	  ungetc(c, fin);
	}
    }
  return eol;
}