Это быстрее, сортировка массива структур или сортировка списка структур C?

Question

Я столкнулся с проблемой. У меня есть данные по связанному списку структур. Переместить данные в массив структур, затем отсортировать его с помощью qsort() или использовать сортировку слияния? Это структура:

struct properties{ 
    char *path; 
    char *name; 
    char *extension; 
    long int size; 
    long unsigned created; 
    long unsigned modified; 
    long unsigned access; 
    int permissions; 
}; 

Answer 1

Я хотел бы создать массив указателей на структуры и отсортировать массив указателей с помощью qsort. Использование указателей для копирования всех структур будет использовать меньше памяти.

Создать компаратор как это:

int propertyComparator(const void *s1, const void* s2) { 
    struct property *p1 = (struct property *)s1, *p2 = (struct property *)s2; 

    /* compare p1 and p2, below is just an example */ 
    int result = strcmp(p1->name, p2->name); 
    return result; 
} 

Называйте это как это:

struct property *array; 
/* add code to allocate and create array */ 
qsort(array, num_elements, sizeof array, propertyComparator); 

Edit:

Если вы хотите иметь упорядоченный связанный список, сортировка слиянием о настолько быстро. Кажется, это зависит от того, насколько фрагментирован связанный список. https://stackoverflow.com/a/1525419/646887

Причина, по которой я предпочитаю qsort, состоит в том, что она является частью C lib, поэтому мне не нужно писать и поддерживать столько кода. И это всегда быстрый выбор.