3

For my project I have a hashtable with 1M buckets (sometimes more).

Each bucket contains lots of values and they are stored sorted in a dynamic array.

I am looking for easy enough way to store all values in a file (printf will do as well), but in sorted way.

Is there a way to do so in less N*N complexity (e.g. merging all 1M arrays/buckets)

4
  • N is number of elements. Hashtable fits in memory. Buckets are fixed and because of this usually will be 1M or more. Count of the elements - unknown – Nick Jan 18 '15 at 20:42
  • What's the type of elements you are sorting over. Is a Radix Sort suitable? – BlamKiwi Jan 19 '15 at 5:46
  • elements are strings, but I am curious how radix can help – Nick Jan 19 '15 at 5:59
  • please ignore me, I overlooked the fact that the sub arrays are sorted. As Ixrec suggests MergeSort (K-Way even) or Polyphase is likely to be the best solution. – BlamKiwi Jan 19 '15 at 9:50
4

I believe the second half of the mergesort algorithm is what you're looking for, since the first half is splitting the numbers into subranges, and the second half is merging those subranges. Mergesort as a whole has a complexity of O(n log n), and I believe the second half by itself would also be O(n log n).

To get you started, here's a reasonably short and readable implementation of mergesort in C, taken from http://www.cquestions.com/2011/07/merge-sort-program-in-c.html

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

    int merge[MAX],i,n;

    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }

    partition(merge,0,n-1);

    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }

   return 0;
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }

    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}

Sample output:

Enter the total number of elements: 5
Enter the elements which to be sort: 2 5 0 9 1
After merge sorting elements are: 0 1 2 5 9

Note that ratchet freak's suggestion is basically the heapsort algorithm, which is also O(n log n), so that one should be fine too.

1

You can make a min-heap where you store all buckets sorted by the first element.

Then you pop an element from the first bucket and re-heapify.

If you are not allowed to change the buckets then keep an index per bucket of which element still has to be popped from it.

5
  • This is what I am thinking about, but would'n this be N*N ? I will need one loop over all buckets in order to produce 1 element for output. for N elements, I will need N loops? – Nick Jan 18 '15 at 19:30
  • no building the heap is O(m*log m) then popping and reheapifying is log(m) each time N times so total time will be O(n*log(m) + m*log(m)) – ratchet freak Jan 18 '15 at 19:34
  • @ratchetfreak What is m? If it's the number of buckets, for most hash tables (those aiming for constant time operations), the number of buckets is linear in n, so for the purposes of big Oh, O(n*log(m) + m*log(m)) = O(n*log(n)). – user7043 Jan 18 '15 at 19:39
  • @delnan he didn't give a relation just "lots" per bucket; log m or log n is way better than his n² either way; – ratchet freak Jan 18 '15 at 19:51
  • lots per bucket means client selects the buckets and they are never changed - similar to tokyo cabinet. this is the reason to select 1M buckets – Nick Jan 18 '15 at 20:25
1

From what you wrote, I don't see a reason why original information about the hashtable and the buckets has to be used - it just overcomplicates things.

So flatten all buckets into a list (complexity O(N)) and apply an arbitrary sorting algorithm with complexity O(N * log(N)), for example, quick sort or merge sort. Then write the results into a file.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.