An include file for the relative spiffy merge sort. Run the file as is for some,
boring, demo output.


ingo


---%<------%<------%<---
/*
 POV-Ray 3.7 Scene File " mergesort.inc"
 author:  Ingo Janssen
 date:    2024-05-26

 Merge sort in two versions, one that returns a sorted array,
 one that results in a sorted index to the original array.
*/

#version 3.7;
//#global_settings{ assumed_gamma 1.0 }
//#default{ finish{ ambient 0.1 diffuse 0.9 }}


#macro MergeSort(ValArr)
  #local Len = dimension_size(ValArr, 1);
  #if (Len <= 1)
    #local Result = ValArr;
  #else
    #local Mid = div(Len, 2);

    #local Left = array[Mid]
    #local I = 0;
    #for(J, 0, Mid - 1)
      #local Left[I] = ValArr[J];
      #local I = I + 1;
    #end

    #local Right = array[Len - Mid]
    #local I = 0;
      #for(J, Mid, Len - 1)
      #local Right[I] = ValArr[J];
      #local I = I + 1;
    #end

    #local Left = MergeSort(Left);
    #local Right = MergeSort(Right);
    #local Result = array[Len];


    #local I = 0;
    #local J = 0;
    #local K = 0;

    #while (I < dimension_size(Left, 1) & J < dimension_size(Right, 1))
      #if (Left[I] < Right[J])
        #local Result[K] = Left[I];
        #local I = I + 1;
      #else
        #local Result[K] = Right[J];
        #local J = J + 1;
      #end
      #local K = K + 1;
    #end

    #local M = I;
    #while (M < dimension_size(Left, 1))
      #local Result[K] = Left[M];
      #local M = M + 1;
      #local K = K + 1;
    #end
    #local M = J;
    #while (M < dimension_size(Right, 1))
      #local Result[K] = Right[M];
      #local M = M + 1;
      #local K = K + 1;
    #end
  #end
  Result
#end


#macro MergeSortByIdx(ValArr, IdxArr)
  /*: MergeSortByIdx(ValArr, IdxArr)
  MergeSortByIdx results in an index array that points to the ValArr in an
ordered way.



  */
  #local Len = dimension_size(IdxArr, 1);
  #if (Len <= 1)
    #local Result = IdxArr;
  #else
    #local Mid = div(Len, 2);

    #local Left = array[Mid]
    #local I = 0;
    #for(J, 0, Mid - 1)
      #local Left[I] = IdxArr[J];
      #local I = I + 1;
    #end

    #local Right = array[Len - Mid]
    #local I = 0;
      #for(J, Mid, Len - 1)
      #local Right[I] = IdxArr[J];
      #local I = I + 1;
    #end

    #local Left = MergeSortByIdx(ValArr, Left);
    #local Right = MergeSortByIdx(ValArr, Right);
    #local Result = array[Len];


    #local I = 0;
    #local J = 0;
    #local K = 0;

    #while (I < dimension_size(Left, 1) & J < dimension_size(Right, 1))
      #if (ValArr[Left[I]] < ValArr[Right[J]])
        #local Result[K] = Left[I];
        #local I = I + 1;
      #else
        #local Result[K] = Right[J];
        #local J = J + 1;
      #end
      #local K = K + 1;
    #end

    #local M = I;
    #while (M < dimension_size(Left, 1))
        #local Result[K] = Left[M];
        #local M = M + 1;
        #local K = K + 1;
    #end

    #local M = J;
    #while (M < dimension_size(Right, 1))
        #local Result[K] = Right[M];
        #local M = M + 1;
        #local K = K + 1;
    #end
  #end
  Result
#end


#if(input_file_name="mergesort.inc")

  #declare StrVals = array[16] {"4", "3", "2", "2", "2", "4", "5", "1", "9",
"7", "7", "5", "6", "1", "8", "9"};
  #declare Vals =    array[16] {4, 3, 2, 2, 2, 4, 5, 1, 9, 7,  7,  5,  6,  1,
8,  9};
  #declare ValsIdx = array[16] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14, 15};

  #declare OddStrVals = array[15] {"4", "3", "2", "2", "2", "4", "5", "1", "9",
"7", "7", "5", "6", "1", "8"};
  #declare OddVals =    array[15] {4, 3, 2, 2, 2, 4, 5, 1, 9, 7,  7,  5,  6,  1,
 8};
  #declare OddValsIdx = array[15] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13,
14};

  #declare SortedVals = MergeSort(StrVals);
  #for(I,0, dimension_size(StrVals,1)-1)
    #debug concat(SortedVals[I],", ")
  #end
  #debug "\n"

  #declare SortedVals = MergeSort(Vals);
  #for(I,0, dimension_size(Vals,1)-1)
    #debug concat(str(SortedVals[I],0,0),", ")
  #end
  #debug "\n"

  #declare IdxSortedVals = MergeSortByIdx(Vals, ValsIdx);
  #for(I, 0, dimension_size(ValsIdx, 1) - 1)
      #debug concat(str(Vals[IdxSortedVals[I]], 0, 0), ", ")
  #end
  #debug "\n"


  #declare OddSortedVals = MergeSort(OddStrVals);
  #for(I,0, dimension_size(OddStrVals,1)-1)
    #debug concat(OddSortedVals[I],", ")
  #end
  #debug "\n"


  #declare OddSortedVals = MergeSort(OddVals);
  #for(I,0, dimension_size(OddVals,1)-1)
    #debug concat(str(OddSortedVals[I],0,0),", ")
  #end
  #debug "\n"

  #declare OddIdxSortedVals = MergeSortByIdx(OddVals, OddValsIdx);
  #for(I, 0, dimension_size(OddValsIdx, 1) - 1)
      #debug concat(str(OddVals[OddIdxSortedVals[I]], 0, 0), ", ")
  #end
  #debug "\n"

#end

---%<------%<------%<---

Post a reply to this message