---
# System prepended metadata

title: Common Sorting Algorithms in C
tags: [coding]

---


# Sort an Array
```(Medium)``` LeetCode [912. Sort an Array](https://leetcode.com/problems/sort-an-array/solutions/5532975/simple-beginner-level-c-solution-merge-sort-quick-sort-insertion-sort-selection-sort/)


## Merge Sort
```cpp
// 912. Sort an Array
void merge_sorted_arrays(int* const arr, const int left, 
                         const int middle, const int right);
void merge_sort_helper(int* const arr, const int left, const int right);
void mergeSort(int* const arr, const int arrSize);

int* sortArray(int* nums, int numsSize, int* returnSize) {
    // Merge Sort

    // Time complexity: O(nlog(n))
    // Space complexity: O(n)

    mergeSort(nums, numsSize);

    *returnSize = numsSize;
    return nums;
}

void merge_sorted_arrays(int* const arr, const int left, 
                         const int middle, const int right) {
    if (arr == NULL) return;
    
    int leftSize = middle - left + 1;
    int rightSize = right - middle;
    
    int temp_left[leftSize];
    int temp_right[rightSize];
    
    for (int i = 0; i < leftSize; i++) {
        temp_left[i] = arr[left + i];
    }
    for (int j = 0; j < rightSize; j++) {
        temp_right[j] = arr[middle + 1 + j];
    }
    
    for (int i = 0, j = 0, k = left; k <= right; k++) {
        // copy left, temp_left[i] <= temp_right[j]
        if ((i < leftSize) && ((j >= rightSize) || temp_left[i] <= temp_right[j]))
            arr[k] = temp_left[i++];
        else  // copy right
            arr[k] = temp_right[j++];
    }
}
void merge_sort_helper(int* const arr, const int left, const int right) {
    if (arr == NULL) return;
    if (left >= right) return;
    
    const int middle = left + (right - left) / 2;
    
    merge_sort_helper(arr, left, middle);
    merge_sort_helper(arr, middle + 1, right);
    
    merge_sorted_arrays(arr, left, middle, right);
}
void mergeSort(int* const arr, const int arrSize) {
    if (arr == NULL) return;
    merge_sort_helper(arr, 0, arrSize - 1);
}
```


## Quick Sort
```cpp
// 912. Sort an Array
void swap(int* const a, int* const b) {
    const int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int* const arr, const int low, const int high);
void quick_sort_helper(int* const arr, const int low, const int high);
void quickSort(int* const arr, const int arrSize);

int* sortArray(int* nums, int numsSize, int* returnSize) {
    // Quick Sort

    // Time complexity: O(nlog(n))
    // Space complexity: O(n)

    quickSort(nums, numsSize);

    *returnSize = numsSize;
    return nums;
}

int partition(int* const arr, const int low, const int high) {
    if (arr == NULL) return 0;
    
    int init_pivot_index = low + (rand() % (high - low));
    
    if (init_pivot_index != high) {
        swap(&arr[init_pivot_index], &arr[high]);
    }
    
    const int pivot_value = arr[high];
    
    int i = low;  // new pivot index 
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot_value) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[high]);
    
    return i;
}
void quick_sort_helper(int* const arr, const int low, const int high) {
    if (arr == NULL) return;
    if (low >= high) return;
    
    const int pivot_index = partition(arr, low, high);
    
    quick_sort_helper(arr, low, pivot_index - 1);
    quick_sort_helper(arr, pivot_index + 1, high);
}
void quickSort(int* const arr, const int arrSize) {
    if (arr == NULL) return;
    srand(time(NULL));
    quick_sort_helper(arr, 0, arrSize - 1);
}
```


## Insertion Sort
```cpp
// 912. Sort an Array
int ascend(const int a, const int b) {
    return (a < b);
}
void swap(int* const a, int* const b) {
    const int temp = *a;
    *a = *b;
    *b = temp;
}
void insertionSort(int* const arr, const int arrSize, int (*compare)(int, int)) {
    for (int i = 1; i < arrSize; i++) {
        const int key = arr[i];
        int j = i - 1;
        while (j >= 0 && compare(key, arr[j])) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
    // Insertion Sort

    // Time complexity: O(n(n - 1)/2) --> O(n^2)
    // Space complexity: O(1)

    insertionSort(nums, numsSize, ascend);

    *returnSize = numsSize;
    return nums;
}
```

## Selection Sort
```cpp
// 912. Sort an Array
int ascend(const int a, const int b) {
    return (a < b);
}
void swap(int* const a, int* const b) {
    const int temp = *a;
    *a = *b;
    *b = temp;
}
void selectionSort(int* const arr, const int arrSize, int (*compare)(int, int)) {
    for (int i = 0; i < arrSize - 1; i++) {
        int swap_pos = i;
        for (int j = i + 1; j < arrSize; j++) {
            swap_pos = compare(arr[j], arr[swap_pos]) ? j : swap_pos;
        }
        if (swap_pos != i) swap(&arr[swap_pos], &arr[i]);
    }
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
    // Selection Sort

    // Time complexity: O(n(n - 1)/2) --> O(n^2)
    // Space complexity: O(1)

    selectionSort(nums, numsSize, ascend);

    *returnSize = numsSize;
    return nums;
}
```

