package main

import (
	"fmt"
	"math/rand"
	"sort"
	"sync"
	"time"
)

/*
*
* Sorts a slice of float64 values using the merge sort algorithm in parallel with channels.
*
*  @param data The slice of float64 values to be sorted.
*  @param sorted The output channel where the sorted values will be sent. This channel should be buffered to avoid blocking.
*  The function will close this channel when sorting is complete.
 */
func mergeSortChannelsInternal(data []float64, sorted chan<- float64) {

	// close the sorted channel when we're done sending sorted values. This ensures that the receiver can detect when all sorted values have been sent and can stop waiting for more data.
	defer close(sorted)

	if len(data) <= 10000 {
		// For small slices, sort them sequentially to avoid the overhead of creating goroutines and channels. This threshold is chosen to balance the overhead of concurrency with the benefits of parallelism.
		sortedData := make([]float64, len(data))
		copy(sortedData, data)
		mergeSortSequential(sortedData)

		// Send sorted values to the output channel. We iterate over the sorted slice and send each value to the sorted channel.
		for _, x := range sortedData {
			sorted <- x
		}
	} else {
		// For larger slices, split them into two halves and sort each half in parallel using channels.
		mid := len(data) / 2
		left := data[:mid]
		right := data[mid:]

		sortedLeft := make(chan float64, 1000)
		sortedRight := make(chan float64, 1000)

		go mergeSortChannelsInternal(left, sortedLeft)
		go mergeSortChannelsInternal(right, sortedRight)

		// Merge the sorted halves and send the merged sorted values to the output channel.
		mergeChannels(sortedLeft, sortedRight, sorted)
	}
}

/**
 * Merges two sorted channels into a single sorted channel.
 *
 * @param a   The first sorted channel.
 * @param b   The second sorted channel.
 * @param out The output channel where the merged sorted values will be sent. This channel should be buffered to avoid blocking.
 */
func mergeChannels(a, b <-chan float64, out chan<- float64) {
	var okA, okB bool
	var valA, valB float64

	for {
		// If we don't have a value from channel a, try to read from it.
		if !okA {
			valA, okA = <-a
		}

		// If we don't have a value from channel b, try to read from it.
		if !okB {
			valB, okB = <-b
		}

		// If both channels are closed and we've read all values, break the loop.
		if !okA && !okB {
			break
		}

		// If one channel is closed, we can only read from the other channel.
		if !okA {
			out <- valB
			okB = false
			continue
		}

		if !okB {
			out <- valA
			okA = false
			continue
		}

		// Both channels have values, compare them and send the smaller one to the output channel.
		if valA < valB {
			out <- valA
			okA = false
		} else {
			out <- valB
			okB = false
		}
	}
}

/**
 * Sorts a slice of float64 values using the merge sort algorithm in parallel with channels.
 *
 * @param data The slice of float64 values to be sorted. The sorting is done in-place, so the original slice will be modified.
 */
func mergeSortChannels(data []float64) {
	sorted := make(chan float64, 1000)
	go mergeSortChannelsInternal(data, sorted)

	sortedData := make([]float64, len(data))
	i := 0
	for x := range sorted {
		sortedData[i] = x
		i++
	}

	copy(data, sortedData)
}

/**
 * Sorts a slice of float64 values using the merge sort algorithm in parallel.
 *
 * @param data The slice of float64 values to be sorted. The sorting is done in-place, so the original slice will be modified.
 */
func mergeSortParallel(data []float64) {

	// Base case: if the slice has 10000 or fewer elements, sort it sequentially. This threshold is chosen to balance
	// the overhead of creating goroutines with the benefits of parallelism. For small slices, the overhead of goroutines
	// may outweigh the performance gains, so we sort them sequentially.
	if len(data) <= 10000 {
		mergeSortSequential(data)
		return
	}

	// Split the slice into two halves. The mid index is calculated as the length of the data divided by 2, which gives us the midpoint of the slice.
	mid := len(data) / 2
	left := data[:mid]
	right := data[mid:]

	// Use a WaitGroup to wait for both halves to be sorted before merging. The WaitGroup allows us to synchronize the completion
	// of the two goroutines that will sort the left and right halves in parallel.
	var wg sync.WaitGroup
	wg.Add(2)

	// Sort left and right halves in parallel using goroutines. Each goroutine will call mergeSortParallel
	// on its respective half and then signal when it's done using the WaitGroup.
	go func() { mergeSortParallel(left); wg.Done() }()
	go func() { mergeSortParallel(right); wg.Done() }()

	wg.Wait()

	copy(data, merge(left, right))
}

/**
 * Sorts a slice of float64 values using the merge sort algorithm sequentially.
 *
 * @param data The slice of float64 values to be sorted. The sorting is done in-place, so the original slice will be modified.
 */
func mergeSortSequential(data []float64) {

	// Base case: if the slice has 0 or 1 element, it's already sorted.
	if len(data) <= 1 {
		return
	}

	// Recursive case: split the slice into two halves, ...
	mid := len(data) / 2
	left := data[:mid]
	right := data[mid:]

	// ... sort each half recursively, ...
	mergeSortSequential(left)
	mergeSortSequential(right)

	// ... and then merge the sorted halves back together.
	copy(data, merge(left, right))
}

/**
 * Merges two sorted slices into a single sorted slice.
 *
 * @param left  The first sorted slice.
 * @param right The second sorted slice.
 * @return A new slice containing all elements from both input slices, sorted in ascending order.
 */
func merge(left, right []float64) []float64 {
	// Create a new slice to hold the merged result. The capacity is set to the sum of the lengths of left and right for efficiency.
	result := make([]float64, 0, len(left)+len(right))
	i, j := 0, 0

	// Merge elements from left and right until one of the slices is exhausted.
	for i < len(left) && j < len(right) {
		if left[i] < right[j] {
			// Append the smaller element from left to the result and move the pointer i.
			result = append(result, left[i])
			i++
		} else {
			// Append the smaller element from right to the result and move the pointer j.
			result = append(result, right[j])
			j++
		}
	}

	// Append any remaining elements from left or right. The ... operator is used to expand the slice into individual elements.
	result = append(result, left[i:]...)
	result = append(result, right[j:]...)

	return result
}

func main() {

	//1. DATA CREATION
	data := make([]float64, 1000*1000*20) //*1000*20)

	for i := range data {
		data[i] = rand.Float64() * 100 // Random floats between 0 and 100
	}

	expected := make([]float64, len(data))
	copy(expected, data)
	sort.Float64s(expected)

	//2. SORTING
	start := time.Now()

	//mergeSortSequential(data)
	//mergeSortParallel(data)
	mergeSortChannels(data)

	elapsed := time.Since(start)
	fmt.Printf("MergeSort took %s\n", elapsed)

	//3. VERIFICATION
	if sort.Float64sAreSorted(data) {
		fmt.Println("Data is sorted correctly")
	} else {
		fmt.Println("Data is NOT sorted correctly")
	}

	if len(data) != len(expected) {
		fmt.Println("Data and expected slices have different lengths")
		return
	}

	for i := range data {
		if data[i] != expected[i] {
			fmt.Println("Data and expected slices do not match")
			return
		}
	}

	fmt.Println("Data and expected slices match")
}