List of articles

• Merge sort ( Merge sort )
• • C++
  • python

Merge sort ( Merge sort )

C++

#include <iostream>
#define N 10
using namespace std;
void merge(int A[], int low, int mid, int high)
{

// Request an auxiliary array 
int* B = new int[high - low + 1];
int i = low, j = mid + 1, k = 0;
// Save in auxiliary array from small to large B[] in 
while (i <= mid && j<=high)
{

if (A[i] <= A[j]) B[k++] = A[i++];
else B[k++] = A[j++];
}
// If the subsequence remains , Move remaining to B[]
while (i <= mid) B[k++] = A[i++];
while (j <= high) B[k++] = A[j++];
// Copy the merged sequence to A[]
for (i = low, k = 0; i <= high; i++)
A[i] = B[k++];
// Delete auxiliary array 
delete []B;
}
void mergeSort(int A[], int low, int high)
{

if (low < high)
{

int mid = (low + high) / 2;
// Yes A[low:mid] Elements in sorting 
mergeSort(A, low, mid);
// Yes A[mid+1:high] Elements in sorting 
mergeSort(A, mid + 1, high);
// Merge 
merge(A, low, mid, high);
}
}
int main()
{

int numbers[N] = {
 3,2,1,5,6,2,8,6,9,7 };
mergeSort(numbers, 0,N-1);
for (int i = 0; i < N; i++)
cout << numbers[i] << " ";
cout << "\n";
return 0;
}

python

def merge(A, low_index, mid, high_index):
B = []
i = low_index
j = mid + 1
while (i <= mid) and (j <= high_index):
if A[i] <= A[j]:
B.append(A[i])
i += 1
else:
B.append(A[j])
j += 1
while i <= mid:
B.append(A[i])
i += 1
while j <= high_index:
B.append(A[j])
j += 1
A[low_index:high_index+1] = B
def merge_sort(A:List[int], low_index, high_index):
if low_index < high_index:
mid = int((low_index + high_index) / 2)
merge_sort(A, low_index, mid)
merge_sort(A, mid + 1, high_index)
merge(A, low_index, mid, high_index)
if __name__ == '__main__':
r = [3, 2, 1, 5, 6, 2, 8, 6, 9, 7]
merge_sort(r, 0, 9)
print(r)