# Sort an Array

## Merge Sort

// 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

// 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

// 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

// 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;
}