# 912. Sort an Array

題目：<https://leetcode.com/problems/sort-an-array/>

解法：實作 merge sort

Python3：

class Solution:
    def sortArray(self, nums: list[int]) -> list[int]:
        if len(nums) <= 1:
            return nums

        pivot = len(nums) // 2
        leftNums = self.sortArray(nums[:pivot])
        rightNums = self.sortArray(nums[pivot:])

        output = []
        leftIdx = rightIdx = 0
        leftLen = len(leftNums)
        rightLen = len(rightNums)
        while leftIdx < leftLen and rightIdx < rightLen:
            if leftNums[leftIdx] < rightNums[rightIdx]:
                output.append(leftNums[leftIdx])
                leftIdx += 1
            else:
                output.append(rightNums[rightIdx])
                rightIdx += 1
        output += leftNums[leftIdx:]
        output += rightNums[rightIdx:]
        return output

if __name__ == '__main__':
    nums = [5,1,1,2,0,0]

    ans = Solution().sortArray(nums)
    print(ans)

C：

#include <stdio.h>
#include <stdlib.h>

int* sortArray(int* nums, int numsSize, int* returnSize) {
    *returnSize = numsSize;
    int *output = (int*)malloc(sizeof(int) * numsSize);
    if (numsSize <= 1) {
        for (int i = 0; i < numsSize; i++)
            output[i] = nums[i];
        return output;
    }

    int pivot = numsSize / 2, leftLen, rightLen, leftIdx, rightIdx, outputIdx;
    int *leftNums = sortArray(nums, pivot, &leftLen);
    int *rightNums = sortArray(nums + pivot, numsSize - pivot, &rightLen);

    outputIdx = leftIdx = rightIdx = 0;
    while (leftIdx < leftLen && rightIdx < rightLen) {
        if (leftNums[leftIdx] < rightNums[rightIdx])
            output[outputIdx++] = leftNums[leftIdx++];
        else
            output[outputIdx++] = rightNums[rightIdx++];
    }
    while (leftIdx < leftLen) 
        output[outputIdx++] = leftNums[leftIdx++];
    while (rightIdx < rightLen)
        output[outputIdx++] = rightNums[rightIdx++];
    return output;
}

int main()
{
    int nums[] = {5,1,1,2,0,0};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    
    int returnSize;
    int* ans = sortArray(nums, numsSize, &returnSize);
    printf("%d\n", returnSize);
    for (int i = 0; i < returnSize; i++)
        printf("%d ", ans[i]);
    printf("\n");
    return 0;
}

###### tags: `leetcode` `array` `sort` `divide and conquer`