Слияние сортировки для связанного списка слишком медленно

Question

Моя задача - прочитать файл и отсортировать его, используя одноуровневый список. Я реализовал сортировку слияния, но система тестирования говорит, что она слишком медленная для больших файлов. Как я могу это оптимизировать?

void merge_sort(list *a, list *tmp, int n) { 
    int k, i, rcount; 
    list *cursor, *l, *r, *end; 
    k = n/2; 
    if(n == 1) { 
     return; 
    } 
    l = a; 
    end = list_get(a, k); 
    r = end; 
    merge_sort(a, tmp, k); 
    merge_sort(r, tmp, n - k); 
    rcount = k; 
    for(cursor = tmp, i = 0; i < n; cursor = cursor->next, i++) { 
     if((l != end) && (((rcount == n) || (strcmp(l->value, r->value) < 0)))) { 
      cursor->value = l->value; 
      l = l->next; 
     } else { 
      cursor->value = r->value; 
      r = r->next; 
      rcount++; 
     } 
    } 
    for(cursor = tmp, i = 0; i < n; cursor = cursor->next, a = a -> next, i++) { 
     a->value = cursor->value; 
    } 
    return; 
} 

Answer 1

Я предполагаю, что требование, чтобы отсортировать список, не сортировать данные в пределах узлов (которые можно было бы сделать путем создания массива указателей на узлы и с помощью слияния/быструю сортировку через массив указателей для переупорядочения данных в узлах).

Использование слияния сверху вниз и быстрого сортировки не является хорошим подходом для связанных списков из-за всего сканирования, выполненного для эмулирования итераторов произвольного доступа, чтобы рекурсивно разбить список.

Подход снизу намного быстрее. Вы можете использовать 4 указателя на узлы в качестве указателей на 4 списка и реализовать что-то вроде сортировки ленты, но для этого нужно использовать счетчики для отслеживания логических концов прогонов в каждом списке. Wiki статьи:

http://en.wikipedia.org/wiki/Merge_sort#Use_with_tape_drives

Это проще и быстрее, по-прежнему использовать небольшой (26 на 32), массив указателей. Это алгоритм, используемый в стандартной библиотеке шаблонов HP/Microsoft для сортировки списка. Wiki статьи:

http://en.wikipedia.org/wiki/Merge_sort#Bottom-up_implementation_using_lists

Пример кода. В моей системе Intel 2600K 3.4ghz он может сортировать 4 миллиона узлов с псевдослучайными 32-разрядными целыми без знака в качестве данных примерно за секунду.

/* prototype */ 
NODE * MergeLists(NODE *pSrc1, NODE *pSrc2); 

/* sort list using array of pointers to first nodes of list */ 
/* aList[i] = NULL or ptr to list with 2 to the power i nodes */ 

#define NUMLISTS 32     /* size of array */ 
NODE * SortList(NODE *pList) 
{ 
NODE * aList[NUMLISTS];    /* array of lists */ 
NODE * pNode; 
NODE * pNext; 
int i; 
    if(pList == NULL)    /* check for empty list */ 
     return NULL; 
    for(i = 0; i < NUMLISTS; i++) /* zero array */ 
     aList[i] = NULL; 
    pNode = pList;     /* merge nodes into array */ 
    while(pNode != NULL){ 
     pNext = pNode->next; 
     pNode->next = NULL; 
     for(i = 0; (i < NUMLISTS) && (aList[i] != NULL); i++){ 
      pNode = MergeLists(aList[i], pNode); 
      aList[i] = NULL; 
     } 
     if(i == NUMLISTS)   /* don't go past end of array */ 
      i--; 
     aList[i] = pNode; 
     pNode = pNext; 
    } 
    pNode = NULL;     /* merge array into one list */ 
    for(i = 0; i < NUMLISTS; i++) 
     pNode = MergeLists(aList[i], pNode); 
    return pNode; 
} 

/* mergelists - compare uses src2 < src1   */ 
/* instead of src1 <= src2 to be similar to C++ STL */ 

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2) 
{ 
NODE *pDst = NULL;     /* destination head ptr */ 
NODE **ppDst = &pDst;    /* ptr to head or prev->next */ 
    if(pSrc1 == NULL) 
     return pSrc2; 
    if(pSrc2 == NULL) 
     return pSrc1; 
    while(1){ 
     if(pSrc2->data < pSrc1->data){ /* if src2 < src1 */ 
      *ppDst = pSrc2; 
      pSrc2 = *(ppDst = &(pSrc2->next)); 
      if(pSrc2 == NULL){ 
       *ppDst = pSrc1; 
       break; 
      } 
     } else {      /* src1 <= src2 */ 
      *ppDst = pSrc1; 
      pSrc1 = *(ppDst = &(pSrc1->next)); 
      if(pSrc1 == NULL){ 
       *ppDst = pSrc2; 
       break; 
      } 
     } 
    } 
    return pDst; 
}