java/sorting/MergeSortNonRecursive.java at master · AllAlgorithms/java · GitHub

This repository was archived by the owner on Sep 7, 2025. It is now read-only.

History

56 lines (48 loc) · 948 Bytes

Raw

public class NonRecursiveMergeSort<T extends Comparable<T>> {

public T[] MergeSort(T[] M) {

int length = M.length;

int size = 1;

int p;

while (size < length) {

p = -1;

while (p + size < length) {

int left = p + 1;

int right = left + size - 1;

if (right + size <= length) {

p = right + size;

} else {

p = length;

}

merge(M, left, right, p);

}

size = size * 2;

}

return M;

}

public T[] merge(T[] M, int left, int right, int p) {

int i = left;

int j = right + 1;

int k = left;

T[] M2 = M.clone();

for (int n = 0; n < M.length; n++) {

M2[n] = null;

}

while (i <= right && j <= p) {

if (M[i].compareTo(M[j]) <= 0) {

M2[k] = M[i];

i = i + 1;

} else {

M2[k] = M[j];

j = j + 1;

}

k = k + 1;

}

for (int h = i; h <= right; h++) {

M[k + (h - i)] = M[h];

}

for (int h = left; h <= (k - 1); h++) {

M[h] = M2[h];

}

return M;

}

java/sorting/MergeSortNonRecursive.java at master · AllAlgorithms/java · GitHub

Uh oh!

Expand file tree

Breadcrumbs

MergeSortNonRecursive.java

Latest commit

History

Breadcrumbs

MergeSortNonRecursive.java

File metadata and controls