Did I come up with new sort algorithm, or does it already exist?

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

Leave a Comment