hi there,
i'm programming an algorythm that sorts p sorted arrays into one array of size n.
this is done on parallel with p processors.
each processor gets an array of size n/p .
the algorythm:
1)each little array has a pointer to its first item which is the smallest (the little arrays are already sorted).
2)compare each pointer of each processor
and find the minimum.
3)the minimum is copied to the final sorted array.
4)the pointer of the processor that gave the minimum is moved to the next item.all other pointer are on hold.
if we cannot increment this pointer any more,then this processor is out of the loop.
5)goto stage 2
6)until array is full
what's the complexity calculation here?
i found that it is o
. am i right?
i'm programming an algorythm that sorts p sorted arrays into one array of size n.
this is done on parallel with p processors.
each processor gets an array of size n/p .
the algorythm:
1)each little array has a pointer to its first item which is the smallest (the little arrays are already sorted).
2)compare each pointer of each processor
and find the minimum.
3)the minimum is copied to the final sorted array.
4)the pointer of the processor that gave the minimum is moved to the next item.all other pointer are on hold.
if we cannot increment this pointer any more,then this processor is out of the loop.
5)goto stage 2
6)until array is full
what's the complexity calculation here?
i found that it is o
. am i right?