Merge sort using one array

Question

My merge sort algorithm is given below...

As we know this algorithm needs extra memory. Is there any way to do sorting with only one array? (Sorting in a single array.)

My merge sort algorithm is:

//LeftPos = start of left half;
//RightPos = start of right half
void  Merge(int A[ ], int LeftPos, int RightPos, int RightEnd) 
{
    int LeftEnd = RightPos – 1;
    int TmpPos = 1
    int NumElements = RightEnd – LeftPos + 1;
    int TempArray[NumElements];
    while(leftPos <= LeftEnd && RightPos <= RightEnd)
        if(A[LeftPos] <= A[RightPos])
            TmpArray[TmpPos++] = A[LeftPos++];
        else
            TmpArray[TmpPos++] = A[RightPos++];
    while(LeftPos <= LeftEnd)   //Copy rest of first half   
        TmpArray[TmpPos++] = A[LeftPos++];
    while(RightPos <= RightEnd) //Copy rest of second half      TmpArray[TmpPos++] = A[RightPos++];
    for(int i = 1; i <= NumElements; i++) //Copy TmpArray back
        A[LeftPos++] = TmpArray[i];
}

possible duplicate of [How to sort in-place using the merge sort algorithm?](http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm) — Ricky Mutschlechner, Oct 24 '14 at 14:32

score 0 · Answer 1 · edited May 23 '17 at 12:27

0

Check these links:

How to sort in-place using the merge sort algorithm?

Java code which will fit your question:

https://github.com/bakeraj4/In-Place-Merge-Sort/blob/master/mergeMain.java

The technique you are looking for is "in place", for future searches you can use it to find better results in the internet.

edited May 23 '17 at 12:27

Community

1
1

answered Oct 24 '14 at 14:37

Hakes

631
3
13

Merge sort using one array

1 Answers1