I am trying to make new way for merge sort to reduce space to O(log(n))
and reduce best case for O(n)
while keep having stability and worst case of (n Log(n))
C# code:
public static void mergeSortMineInit(List<int> list)
{
int n = list.Count;
int width = 32;
for (int i = 0; i <= n; i += width)
{
insertionSortModified(list, i, Math.Min(i + width, n));
}
while (width <= n)
{
int width2T = 2 * width;
for (int i = 0; i <= n; i += width2T)
{
merge(list, i, Math.Min(i + width, n - 1), Math.Min(i + width2T, n));
}
width = width2T;
}
}
public static void insertionSortModified(List<int> arr, int startIndex, int endIndex)
{
for (int i = startIndex + 1; i < endIndex; i++)
{
int key = arr[i];
int j = i - 1;
while (startIndex <= j && key < arr[j])
{
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
public static void merge(List<int> list, int start, int mid, int end)
{
int? amountOfItems = kthElementAmount(
list: list,
start: start,
midEnd: mid,
mid: mid,
end: end
);
if (amountOfItems == null)
{
return;
}
int newMidIndex = mid - amountOfItems.Value;
int i = newMidIndex;
int j = mid;
for (; j < mid + amountOfItems; i++, j++)
{
int temp = list[j];
list[j] = list[i];
list[i] = temp;
}
merge(list, start, newMidIndex, mid); //m-amount,m
merge(list, mid, mid + amountOfItems.Value, end); //amount,n
}
public static int? kthElementAmount(List<int> list, int start, int midEnd, int mid, int end, bool isNormal = true)
{
int list1Size = midEnd - start;
int list2Size = end - mid;
if (Math.Min(list1Size, list2Size) <= 16)
{
miniSort(list: list, start: start, mid: mid, end: end);
return null;
}
if (list1Size > list2Size)
{
return kthElementAmount(list: list, start: mid, midEnd: end, mid: start, end: midEnd, isNormal: false);
}
int k = isNormal ? list1Size : list2Size;
int low = 0;
int high = list1Size;
Func<int?, int?, bool> l1r2Func;
Func<int?, int?, bool> l2r1Func;
if (isNormal)
{
l1r2Func = (l1, r2) => l1 == null || r2 == null || l1 <= r2;
l2r1Func = (l2, r1) => l2 == null || r1 == null || l2 < r1;
}
else
{
l1r2Func = (l1, r2) => l1 == null || r2 == null || l1 < r2;
l2r1Func = (l2, r1) => l2 == null || r1 == null || l2 <= r1;
}
while (low <= high)
{
int cut = (low + high) >> 1;
int cut1 = cut + start;
int cut2 = (k - cut) + mid;
int? l1Index = cut1 == start ? null : cut1 - 1;
int? l1 = l1Index == null ? null : list[l1Index.Value]; //MIN_VALUE
int? r1 = cut1 == midEnd ? null : list[cut1]; //MAX_VALUE
//
int? l2Index = cut2 == mid ? null : cut2 - 1;
int? l2 = l2Index == null ? null : list[l2Index.Value]; //MIN_VALUE
int? r2 = cut2 == end ? null : list[cut2]; //MAX_VALUE
bool l1r2Bool = l1r2Func(l1, r2);
bool l2r1Bool = l2r1Func(l2, r1);
if (l1r2Bool && l2r1Bool)
{
if (isNormal)
{
return l2Index == null ? null : l2Index - mid + 1; //amount
}
else
{
return l1Index == null ? null : l1Index - start + 1; //amount
}
}
else if (!l1r2Bool)
{
high = cut - 1;
}
else
{
low = cut + 1;
}
}
throw new Exception("Incorrect input??!!");
}
public static void miniSort(List<int> list, int start, int mid, int end)
{
List<int> tempList = new List<int>();
if (start > mid)
{
return;
}
if (end - mid < mid - start)
{
//second smaller
for (int j = mid; j < end; j++)
{
tempList.Add(list[j]);
}
int listIndex = mid - 1;
int tempIndex = tempList.Count - 1;
int counter = end - 1;
for (; start <= listIndex && 0 <= tempIndex; counter--)
{
if (tempList[tempIndex] < list[listIndex])
{
list[counter] = list[listIndex];
listIndex--;
}
else
{
list[counter] = tempList[tempIndex];
tempIndex--;
}
}
for (; start <= listIndex; counter--)
{
list[counter] = list[listIndex];
listIndex--;
}
for (; 0 <= tempIndex; counter--)
{
list[counter] = tempList[tempIndex];
tempIndex--;
}
}
else
{
//first smaller
for (int i = start; i < mid; i++)
{
tempList.Add(list[i]);
}
int tempListSize = tempList.Count;
int listIndex = mid;
int tempIndex = 0;
int counter = start;
for (; listIndex < end && tempIndex < tempListSize; counter++)
{
if (tempList[tempIndex] <= list[listIndex])
{
list[counter] = tempList[tempIndex];
tempIndex++;
}
else
{
list[counter] = list[listIndex];
listIndex++;
}
}
for (; listIndex < end; counter++)
{
list[counter] = list[listIndex];
listIndex++;
}
for (; tempIndex < tempListSize; counter++)
{
list[counter] = tempList[tempIndex];
tempIndex++;
}
}
}
Test on list of 3000000 item
Random elements
- Top Down Merge Sort: 0:00:01.322298
- Bottom Up Merge Sort: 0:00:01.794660
- MergeSort Mine: 0:00:03.539161
- Heap Sort: 0:00:04.485955
Sorted elements
- Top Down Merge Sort: 0:00:00.448717
- Bottom Up Merge Sort: 0:00:00.682326
- Merge Sort Mine: 0:00:00.105623
- Heap Sort: 0:00:01.298882