如何在仅用1个额外数组时，实现数组去重与原元素位置还原？

已完成操作：

• 复制原数组Arr到新数组newArr
• 对newArr执行归并排序，确保时间复杂度为O(nlogn)
• 将newArr中的重复元素移至数组末尾

待解决需求：

• 把newArr中的唯一元素还原到原数组Arr中的对应位置，保留元素在原数组的原始位置
• 所有重复元素移至数组末尾（顺序无要求）
• 返回数组中唯一元素的数量
• 仅允许使用Arr和newArr两个数组，尝试过bin_search_first二分查找但未成功，求可行思路

#define _CRT_SECURE_NO_WARNINGS

/*Libraries*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int* input_array(int);
int moveDuplicatesV2(int*, int);
void merge(int* a, int p, int q, int r);
void merge_sort(int* a, int first, int last); 
void swap(int* v, int* u);
int bin_search_first(int , int* , int );


int main()
{
    int arr[10] =  { };
    int n = 12; 
    int k = 0;
    int first = 0;
    int last = n - 1;
    int mid = (first + last) / 2;
    int l = n - 1;
    int* D = arr + 1;
    int j = 0;
    size_t dupes_found = 0;
    int* newArr = (int*)malloc(12 * sizeof(int));
    assert(newArr);
    for (int i = 0; i < n; i++)
    {
        newArr[i] = arr[i];
    }
    merge_sort(newArr, first, last);
    for (size_t i = 0; i < n - 1 - dupes_found;) 
    {
        if (newArr[i] == newArr[i + 1])
        {
            dupes_found++;
            int temp = newArr[i];
            memmove(&newArr[i], &newArr[i + 1], sizeof(int) * (n - i - 1));
            newArr[n - 1] = temp;
        }
        else {
            i++;
        }
    }
    j = 0;
    int key = 0;
    first = 0;
    for (int i = 0; i < n - dupes_found; i++)
    {
        key = newArr[i];
        first = bin_search_first(key, arr,n);
        swap(&newArr[i], &newArr[first]);
        newArr[first] = newArr[i];


    }

    for (int i = 0; i < n; i++)
    {
        arr[i] = newArr[i];
    }

    
    for (int i = 0; i < n; i++)
    {
        printf("%d", arr[i]);
    }
    return n - dupes_found;
}
void merge(int* a, int p, int q, int r)
{
    int i = p, j = q + 1, k = 0;
    int* temp = (int*)malloc((r - p + 1) * sizeof(int));
    assert(temp);
    while ((i <= q) && (j <= r))
        if (a[i] < a[j])
            temp[k++] = a[i++];
        else
            temp[k++] = a[j++];
    while (j <= r)
        temp[k++] = a[j++];
    while (i <= q)
        temp[k++] = a[i++];
    /* copy temp[] to a[]   */
    for (i = p, k = 0; i <= r; i++, k++)
        a[i] = temp[k];
    free(temp);
}
void merge_sort(int* a, int first, int last)
{
    int middle;
    if (first < last) {
        middle = (first + last) / 2;
        merge_sort(a, first, middle);
        merge_sort(a, middle + 1, last);
        merge(a, first, middle, last);
    }
}

void swap(int* v, int* u)
{
    int temp;
    temp = *v;
    *v = *u;
    *u = temp;
}
int bin_search_first(int key, int* a, int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2; // low + (high - low) / 2
        if (key > a[mid])
            low = mid + 1;
        else
            if (key < a[mid])
                high = mid - 1;
            else //key==a[mid]
                if ((low == high) || (a[mid - 1] < key))
                    return mid;
                else
                    high = mid - 1;
    }
    return -1;
}

内容的提问来源于stack exchange，提问作者EraoS